题面在最下方。
吐个槽，矩阵我没写long long挂了40分 （事实上正常写法不用long long，但。。我。。不正常）
首先推一下简单的结果找找感觉，就可以得到一个结论：第n个阶段的病毒数An=K^(n-1)
等比数列求和会吗？Sn=S1+S2+...+Sn=1+K+K2+...+Kn-1，由于题目说的是第n阶段前有多少个病毒分裂，那么答案就是Sn-1。
但是我们发现，这个坑逼玩意儿不太好求。
为啥？如果你用求和公式的话，要写个高精度，除啊模啊，想想都头大！如果你不用高精度 ，偏要O（n）枚举求和的话，本题nmax=10^18，那就非常有意思了。
怎么搞？都想到这里了，难道还要放弃？
天无绝人之路，本题解法一就出来了：这玩意可以分治解决！
思路：设问题求的是1 + K + K2 + K3 + ⋯ + KM, 对 此式子分治解决，先求得1 + K + ⋯ + KM/2-1 , 然后KM/2 + ⋯ + KM等于前式乘以KM/2 得到，将两式合并即可，而对于前半部分，递归使用以上算法即可，完美地避开 了除法运算。分治共log(N)层，每层只递归计算一边，然后合并调用快速幂，所 以总的复杂度为 O(log2(N))。
1 #include2 #include 3 using namespace std; 4 #define LL long long 5 LL N, K, P; 6 7 LL ksm(LL x, LL k) { 8 LL res = 1; 9 for (; k>0; x=x*x%P, k>>=1)10 if (k&1) res = res*x%P;11 return res;12 }13 14 LL sum(LL n) {15 if (!n) return 0;16 LL res = sum(n>>1);17 LL res1 = (res + res * ksm(K, n>>1)) % P;18 if (n & 1) return (res1 + ksm(K, n-1)) % P;19 else return res1;20 }21 22 int main()23 {24 freopen("split.in", "r", stdin);25 freopen("split.out", "w", stdout);26 cin >> K >> N >> P;27 K %= P;28 cout << sum(N - 1) << '\n';29 return 0;30 }
解法二：矩阵快速幂
1 #include2 #include 3 using namespace std; 4 template inline void read(T &_a){ 5 int _ch=getchar();_a=0; 6 while(_ch<'0' || _ch>'9')_ch=getchar(); 7 while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();} 8 } 9 10 long long k,n,p; 11 12 struct matrix13 {14 long long a[2][2];15 matrix() {memset(a,0,sizeof(a));}16 matrix operator * (matrix &x) const {17 matrix res;18 for (register int i=0;i<=1;++i)19 for (register int v=0;v<=1;++v)20 for (register int j=0;j<=1;++j)21 res.a[i][v]+=a[i][j]*x.a[j][v],res.a[i][v]%=p;22 return res;23 }24 };25 26 matrix clac(matrix a,long long b)27 {28 matrix res;29 res.a[0][0]=res.a[1][1]=1;30 while(b)31 {32 if(b&1) res=res*a;33 b>>=1;34 a=a*a;35 }36 return res;37 }38 39 int main()40 {41 read(k); read(n); read(p);42 matrix op;43 op.a[0][0]=k; op.a[1][0]=op.a[1][1]=1;44 op=clac(op,n-2);45 long long ans=op.a[1][0]*k%p;46 ans+=op.a[1][1];47 printf("%lld",ans%p);48 return 0;49 }