题目大意
给定矩阵 A,求 A+A2+A3+...+Ak 中每一个数字对 p 取模的结果。
n≤30,k≤109,p≤104。
思路
先把矩阵乘法、加法、快速幂写出来(不做讲解)。
然后写一个函数 f(x),返回值为 A+A2+A3+...+Ax。
先用 f(⌊x/2⌋) 把 A+A2+A3+...+A⌊x/2⌋ 求出来。
假设 res=f(⌊x/2⌋),那么
res×A⌊x/2⌋=(A+A2+A3+...+A⌊x/2⌋)×A⌊x/2⌋=A×A⌊x/2⌋+A2×A⌊x/2⌋+A3×A⌊x/2⌋+...+A⌊x/2⌋×A⌊x/2⌋=A⌊x/2⌋+1+A⌊x/2⌋+2+A⌊x/2⌋+3+...+A⌊x/2⌋+⌊x/2⌋
这样就可以得出:
res+res×A⌊x/2⌋=(A+A2+A3+...+A⌊x/2⌋)+(A⌊x/2⌋+1+A⌊x/2⌋+2+A⌊x/2⌋+3+...+A⌊x/2⌋+⌊x/2⌋)=A+A2+A3+...+A⌊x/2⌋×2
res+res×A⌊x/2⌋
=(A+A2+A3+...+A⌊x/2⌋)+(A⌊x/2⌋+1+A⌊x/2⌋+2+A⌊x/2⌋+3+...+A⌊x/2⌋+⌊x/2⌋)
=A+A2+A3+...+A⌊x/2⌋×2
那么,当 x 为偶数,⌊x/2⌋×2=x,所以 res+res×A⌊x/2⌋ 即为答案。
当 x 为奇数,⌊x/2⌋×2=x−1,所以 res+res×A⌊x/2⌋=A+A2+A3+...+Ax−1,所以这个结果加上 Ax 即为答案。
因为每次递归只需要求 f(⌊x/2⌋),所以时间复杂度为 O(logk)。
摆上代码
1 2 3 4 5 6 7 8 9
| matrix a;
matrix f(int x) { if(x==1) return a; matrix res=f(x/2); if(x%2==0) return res+(qpow(a,x/2)*res); else return res+(res*qpow(a,x/2))+qpow(a,x); }
|
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
| #include<bits/stdc++.h> using namespace std; int n,k,p; struct matrix { int a[35][35]; matrix operator *(matrix b) { matrix res; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { res.a[i][j]=0; for(int k=1;k<=n;k++) { res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j])%p; } } return res; } matrix operator +(matrix b) { matrix res; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) res.a[i][j]=(a[i][j]+b.a[i][j])%p; return res; } };
matrix qpow(matrix a,int k) { matrix res; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) res.a[i][j]=0; for(int i=1;i<=n;i++) res.a[i][i]=1; while(k) { if(k&1) res=res*a; a=a*a; k>>=1; } return res; }
matrix a;
matrix f(int x) { if(x==1) return a; matrix res=f(x/2); if(x%2==0) return res+(qpow(a,x/2)*res); else return res+(res*qpow(a,x/2))+qpow(a,x); }
matrix ans;
signed main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>k>>p; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) cin>>a.a[i][j],a.a[i][j]%=p; ans=f(k); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) cout<<ans.a[i][j]%p<<" "; cout<<endl; } return 0; }
|