Reading comprehension HDU - 4990（矩阵快速幂+构造矩阵）
#include<iostream>
using namespace std;
typedef long long LL;
LL n,m;
struct mat{
LL m[3][3];
};
mat mul(mat a,mat b){
mat ans;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
ans.m[i][j]=0;
for(int k=0;k<3;k++){
ans.m[i][j]+=a.m[i][k]*b.m[k][j];
ans.m[i][j]%=m;
}
}
}
return ans;
}
mat qb(mat a,LL b){
mat ans={
1,0,0,
0,1,0,
0,0,1
};
mat res=a;
while(b){
if(b&1){
ans=mul(ans,res);
}
res=mul(res,res);
b>>=1;
}
return ans;
}
int main(){
while(~scanf("%lld%lld",&n,&m)){
if(n==1) cout<<1%m<<endl;
else if(n==2) cout<<2%m<<endl;
else{
mat ans={
1,2,1,
0,0,0,
0,0,0
};
mat tem={
0,2,0,
1,1,0,
0,1,1
};
tem=qb(tem,n-2);
// for(int i=0;i<3;i++){
// for(int j=0;j<3;j++){
// cout<<tem.m[i][j];
// }
// cout<<endl;
// }
mat s=mul(ans,tem);
cout<<s.m[0][1]%m<<endl;
}
}
}
矩阵一定要是longlong鸭
查看9道真题和解析