解题思路:
快速幂运算和矩阵乘法结合即可
注意事项:
任何矩阵的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语言代码)浏览:744 |
C语言训练-排序问题<1> (C语言代码)浏览:1351 |
川哥的吩咐 (C++代码)浏览:1016 |
字符串输入输出函数 (C++代码)(都当成字符串吧hhhhhhhh)浏览:493 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:623 |
时间转换 (Java代码)浏览:575 |
程序员的表白 (C语言代码)浏览:667 |
DNA (C语言描述,数据结构)浏览:861 |
The 3n + 1 problem (C语言代码)浏览:554 |
数对 (C语言代码)浏览:702 |