矩阵补题、、、、、
矩阵快速幂板子
const int z = 2;
struct ju{
long long a[z][z];
};
ju muli(ju A,ju B,int mod){
ju C;
for(int i=0;i<z;++i){
for(int j=0;j<z;++j){
C.a[i][j]=0;
for(int k=0;k<z;++k){
C.a[i][j]+=A.a[i][k]*B.a[k][j];
C.a[i][j]%=mod;
}
}
}
return C;
}
ju init(){
ju res;
for(int i=0;i<z;++i){
for(int j=0;j<z;++j){
if(i==j)res.a[i][j]=1;
else res.a[i][j]=0;
}
}
return res;
}
ju pow(ju A,int n,int mod){
ju res=init(),temp=A;
for(;n;n/=2){
if(n&1)res=muli(res,temp,mod);
temp=muli(temp,temp,mod);
}
return res;
}
void print(ju A){
for(int i=0;i<z;++i){
for(int j=0;j<z;++j){
cout<<A.a[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
第一题
题目传送门 2019河北省大学生程序设计竞赛（重现赛） B题 题意： 意思大概就是叫你求等比数列的前n项和，其中一种解法就是矩阵快速幂。。。。
/*
s[i]=s[i-1]*q+q;
|s 1|*|q 0|
|0 1| |q 1|
|sq+q 1|
|0 1|
*/
s[i] 表示的就是S, 然后 后面的矩阵是个常量。。。。。
AC 代码
点这里
持续更新。。。。
