快速幂总结
日期：2022年5月20日
注：本博客仅供参考
概念
矩阵是一个按照长方阵列排列的复数或实数集合。由 m × n 个数aij排成的m行n列的数表称为m行n列的矩阵，简称m × n矩阵。
$$\begin{matrix}
0&1&1\\
1&1&0\\
1&0&1\\
\end{matrix}$$代码实现
快速幂及其应用
【模板】快速幂（P1226）
1 #include2 using namespace std; 3 long long a; 4 int b,p; 5 int fast(long long a,int b,int p){ 6 long long s=1%p; 7 while(b) 8 { 9 if(b&1) 10 { 11 s=(s*a)%p; 12 } 13 a=(a*a)%p; 14 b=b>>1; 15 } 16 return s; 17 } 18 int main(){ 19 scanf("%lld%d%d",&a,&b,&p); 20 printf("%d^%d mod %d=%d",a,b,p,fast(a,b,p)); 21 return 0; 22 }
越狱（P3197）
1 #include2 using namespace std; 3 long long n,sum1=0,sum2=0; 4 long long m; 5 int p=100003; 6 int fast(long long a,long long b,int c){ 7 long long s=1%c; 8 while(b) 9 { 10 if(b&1) 11 { 12 s=(s*a)%c; 13 } 14 a=(a*a)%c; 15 b=b>>1; 16 } 17 return s; 18 } 19 int main(){ 20 scanf("%d%lld",&m,&n); 21 sum1=fast(m,n,p); 22 sum2=m*fast(m-1,n-1,p)%p; 23 printf("%d",(sum1-sum2+p)%p); 24 return 0; 25 }
T176737（用快速幂实现）
1 #include2 using namespace std; 3 int x,n,p; 4 long long fast(long long a,int b,int p){ 5 long long s=1%p; 6 while(b) 7 { 8 if(b&1) 9 { 10 s=(s*a)%p; 11 } 12 a=(a*a)%p; 13 b=b>>1; 14 } 15 return s; 16 } 17 long long sum(long long x,int n){ 18 if(n==1) 19 { 20 return x%p; 21 } 22 int s=sum(x,n/2)%p; 23 s=(s+s*fast(x,n/2,p))%p; 24 if(n&1) 25 { 26 s=(s+fast(x,n,p))%p; 27 } 28 return s; 29 } 30 int main(){ 31 scanf("%lld%d%d",&x,&n,&p); 32 printf("%d",sum(x,n)); 33 return 0; 34 }
【模板】矩阵快速幂（P3390）
1 #include2 using namespace std; 3 const int P=1e9+7; 4 int n; 5 long long K; 6 struct matrix{ 7 long long a[105][105]; 8 }; 9 matrix operator *(matrix A,matrix B){ 10 matrix C; 11 memset(C.a,0,sizeof(C.a)); 12 for(int i=1;i<=n;++i) 13 { 14 for(int j=1;j<=n;++j) 15 { 16 for(int k=1;k<=n;++k) 17 { 18 C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%P; 19 } 20 } 21 } 22 return C; 23 } 24 matrix fast(matrix A,long long b){ 25 matrix S=A; 26 --b; 27 while(b) 28 { 29 if(b&1) 30 { 31 S=(S*A); 32 } 33 A=A*A; 34 b=b>>1; 35 } 36 return S; 37 } 38 matrix A; 39 int main(){ 40 scanf("%d%lld",&n,&K); 41 for(int i=1;i<=n;++i) 42 { 43 for(int j=1;j<=n;++j) 44 { 45 scanf("%d",&A.a[i][j]); 46 } 47 } 48 matrix C=fast(A,K); 49 for(int i=1;i<=n;++i) 50 { 51 for(int j=1;j<=n;++j) 52 { 53 printf("%lld ",C.a[i][j]); 54 } 55 printf("\n"); 56 } 57 return 0; 58 }
斐波那契数列（P1962）
1 #include2 using namespace std; 3 const int P=1e9+7; 4 int n; 5 long long K; 6 struct matrix{ 7 long long a[105][105]; 8 }; 9 matrix operator *(matrix A,matrix B){ 10 matrix C; 11 memset(C.a,0,sizeof(C.a)); 12 for(int i=1;i<=n;++i) 13 { 14 for(int j=1;j<=n;++j) 15 { 16 for(int k=1;k<=n;++k) 17 { 18 C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%P; 19 } 20 } 21 } 22 return C; 23 } 24 matrix fast(matrix A,long long b){ 25 matrix S=A; 26 --b; 27 while(b) 28 { 29 if(b&1) 30 { 31 S=(S*A); 32 } 33 A=A*A; 34 b=b>>1; 35 } 36 return S; 37 } 38 matrix A; 39 int main(){ 40 scanf("%d%lld",&n,&K); 41 for(int i=1;i<=n;++i) 42 { 43 for(int j=1;j<=n;++j) 44 { 45 scanf("%d",&A.a[i][j]); 46 } 47 } 48 matrix C=fast(A,K); 49 for(int i=1;i<=n;++i) 50 { 51 for(int j=1;j<=n;++j) 52 { 53 printf("%lld ",C.a[i][j]); 54 } 55 printf("\n"); 56 } 57 return 0; 58 }
T176737（用矩阵实现）
1 #include2 using namespace std; 3 long long x,n,p; 4 struct matrix{ 5 int a[3][3]; 6 }; 7 matrix A; 8 matrix operator *(matrix A,matrix B){ 9 matrix C; 10 memset(C.a,0,sizeof(C.a)); 11 for(int i=1;i<=2;++i) 12 { 13 for(int j=1;j<=2;++j) 14 { 15 for(int k=1;k<=2;++k) 16 { 17 C.a[i][j]=(C.a[i][j]+(A.a[i][k]*B.a[k][j])%p)%p; 18 } 19 } 20 } 21 return C; 22 } 23 matrix fast(matrix A,long long b){ 24 matrix S=A; 25 --b; 26 while(b) 27 { 28 if(b&1) 29 { 30 S=S*A; 31 } 32 A=A*A; 33 b=b>>1; 34 } 35 return S; 36 } 37 int main(){ 38 scanf("%d%d%d",&x,&n,&p); 39 A.a[1][1]=1,A.a[2][1]=1; 40 A.a[1][2]=0,A.a[2][2]=x; 41 matrix C=fast(A,n-1); 42 printf("%d",(x*C.a[1][1]+x*x*C.a[2][1])%p); 43 return 0; 44 }
【模板】矩阵加速（数列）
1 #include2 using namespace std; 3 const int P=1e9+7; 4 int n; 5 long long K; 6 struct matrix{ 7 long long a[105][105]; 8 }; 9 matrix operator *(matrix A,matrix B){ 10 matrix C; 11 memset(C.a,0,sizeof(C.a)); 12 for(int i=1;i<=n;++i) 13 { 14 for(int j=1;j<=n;++j) 15 { 16 for(int k=1;k<=n;++k) 17 { 18 C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%P; 19 } 20 } 21 } 22 return C; 23 } 24 matrix fast(matrix A,long long b){ 25 matrix S=A; 26 --b; 27 while(b) 28 { 29 if(b&1) 30 { 31 S=(S*A); 32 } 33 A=A*A; 34 b=b>>1; 35 } 36 return S; 37 } 38 matrix A; 39 int main(){ 40 scanf("%d%lld",&n,&K); 41 for(int i=1;i<=n;++i) 42 { 43 for(int j=1;j<=n;++j) 44 { 45 scanf("%d",&A.a[i][j]); 46 } 47 } 48 matrix C=fast(A,K); 49 for(int i=1;i<=n;++i) 50 { 51 for(int j=1;j<=n;++j) 52 { 53 printf("%lld ",C.a[i][j]); 54 } 55 printf("\n"); 56 } 57 return 0; 58 }