解题思路:
快速幂运算和矩阵乘法结合即可
注意事项:
任何矩阵的0次方等于单位矩阵
参考代码:
#include<iostream> #include<algorithm> using namespace std; const int MAX=2; typedef struct { int m[MAX][MAX]; }Matrix; Matrix I= { 1,0, 0,1, }; Matrix ZERO= { 0,0, 0,0, }; Matrix matrixmul(Matrix a,Matrix b,int m)//矩阵乘法 { Matrix c; for(int i=0;i<MAX;i++) { for(int j=0;j<MAX;j++) { c.m[i][j]=0; for(int k=0;k<MAX;k++) { c.m[i][j]+=(a.m[i][k]*b.m[k][j])%m; } c.m[i][j]%=m; } } return c; } Matrix quickpow(Matrix p,long long n,int m) { Matrix ans = I; while(n>0) { if(n&1) ans = matrixmul(ans,p,m); n=n>>1; p=matrixmul(p,p,m); } return ans; } void print(Matrix p) { cout<<p.m[0][0]<<" "<<p.m[0][1]<<endl; cout<<p.m[1][0]<<" "<<p.m[1][1]<<endl; } int main(void) { int b,m; Matrix p; cin>>b>>m; if(b!=0) { cin>>p.m[0][0]>>p.m[0][1]>>p.m[1][0]>>p.m[1][1]; p = quickpow(p,b,m); print(p); } else if(b==0 && m!=1) { print(I); } else { print(ZERO); } return 0; }
0.0分
1 人评分
C语言训练-邮票组合问题* (C语言代码)浏览:695 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:822 |
C语言训练-字符串正反连接 (C语言代码)浏览:694 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:1724 |
C语言程序设计教程(第三版)课后习题8.3 (Java代码)浏览:1374 |
回文串 (C语言代码)浏览:2860 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:572 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:857 |
C语言训练-列出最简真分数序列* (C语言代码)浏览:619 |
【蟠桃记】 (C语言代码)浏览:666 |