2025年暑假集训一矩阵乘法
2025年暑假集训一矩阵乘法
优化有限项递推公式时，可以采用矩阵乘法的方式进行优化，优化之处在于用类似快速幂的方式将递推通式转化为对应矩阵，不断递推的关系变成相应的关系矩阵的若干次幂。
举个栗子： 经典的斐波那契数列问题(Fibonacci)
f(0)=0，f(1)=1
n>=2时，f(n)=f(n-1)+f(n-2)
如果要求第n项的Fibonacci值时，未学习矩阵乘法快速幂的方法，很难想出除了单纯公式递推的方法
当n很大时，比如1e12，结果显然已经爆longlong了，题目一般会问 f(n)%mod 的结果，单纯的递推c++代码不可能在合法时间内计算完毕，因此要采用矩阵乘法的快速幂计算形式。
下面会用视频形式讲解Fibonacci的矩阵递推方法，和对应快速幂，以及一些变式(本文下面部分题目的矩阵递推)
腾讯会议
录制: 矩阵乘法
录制文件：https://meeting.tencent.com/crm/KEBXBxM7d2
复制链接到微信，点击后会打开腾讯会议的回放，推荐用电脑打开
推荐用链接，还有字幕和总结
矩阵乘法
下面是几个题目和对应代码，具体题解不再提供（C,D两个偏难）
Problem A:Not Fibonacci
#include<bits/stdc++.h>
typedef long long LL;
const LL maxn = 1000+10;
const LL mod =10000000;
using namespace std;
struct matrix
{LL m[3][3];
};
matrix A;
matrix I={1,0,0,0,1,0,0,0,1};
//矩阵乘法
matrix multi(matrix a,matrix b)
{matrix c;for(int i=0;i<3;i++)for(int j=0;j<3;j++){c.m[i][j]=0;for(int k=0;k<3;k++)c.m[i][j]+=a.m[i][k]*b.m[k][j]%mod;c.m[i][j]%=mod;}return c;
}
//矩阵快速幂
matrix power(matrix A,LL k)
{matrix ans=I,p=A;while(k){if(k&1) ans=multi(ans,p);k>>=1;p=multi(p,p);}return ans;
}
int main()
{int t,a,b,p,q,s,e;cin>>t;while(t--){cin>>a>>b>>p>>q>>s>>e;A.m[0][0]=1;A.m[0][1]=p;A.m[0][2]=q;A.m[1][0]=0;A.m[1][1]=p;A.m[1][2]=q;A.m[2][0]=0;A.m[2][1]=1;A.m[2][2]=0;s--;int s1,s2;if(s<0) s1=0;else if(s==0) s1=a;else{matrix ans=power(A,s-1);s1=(ans.m[0][0]%mod*(a+b)%mod+ans.m[0][1]%mod*b%mod+ans.m[0][2]%mod*a%mod)%mod;}if(e==0) s2=a;else{matrix ans=power(A,e-1);s2=(ans.m[0][0]%mod*(a+b)%mod+ans.m[0][1]%mod*b%mod+ans.m[0][2]%mod*a%mod)%mod;}LL l=((s2-s1)%mod+mod)%mod;cout<<l<<endl;}return 0;
}
Problem B:Another kind of Fibonacci
#include<bits/stdc++.h>
typedef long long LL;
const LL mod =10007;
using namespace std;
struct matrix
{LL m[4][4];
};
matrix A;
matrix I={1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1};
//矩阵乘法
matrix multi(matrix a,matrix b)
{matrix c;for(int i=0;i<4;i++)for(int j=0;j<4;j++){c.m[i][j]=0;for(int k=0;k<4;k++)c.m[i][j]+=a.m[i][k]*b.m[k][j]%mod;c.m[i][j]%=mod;}return c;
}
//矩阵快速幂
matrix power(matrix A,LL k)
{matrix ans=I,p=A;while(k){if(k&1) ans=multi(ans,p);k>>=1;p=multi(p,p);}return ans;
}
int main()
{int n,x,y;while(scanf("%d %d %d",&n,&x,&y)!=EOF){memset(A.m,0,sizeof(A.m));x%=mod;y%=mod;A.m[0][0] = 1;A.m[0][1] = x*x%mod;A.m[0][2] = y*y%mod;A.m[0][3] = 2*x*y%mod;A.m[1][1] = x*x%mod;A.m[1][2] = y*y%mod;A.m[1][3] = 2*x*y%mod;A.m[2][1] = 1;A.m[2][2] = 0;A.m[3][1] = x%mod;A.m[3][2] = 0;A.m[3][3] = y%mod;matrix temp=power(A,n-1);LL ans=(temp.m[0][0]*2%mod+temp.m[0][1]*1%mod+temp.m[0][2]*1%mod+temp.m[0][3]*1%mod)%mod;cout<<ans<<endl;}return 0;
}
Problem C:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct matrie{LL m[60][60];
};
matrie A,I;
void pascal(LL k){for(LL i=1;i<k+2;i++){A.m[i][k+1]=1;A.m[i][k+2-i]=1;}for(LL i=1;i<k+2;i++){for(LL j=k+3-i;j<k+1;j++){A.m[i][j]=A.m[i-1][j]+A.m[i-1][j+1];}}
}
LL pow(LL a,LL p,LL mod){LL ans=1;a=a%mod;while(p--) ans=ans*a%mod;return ans;
}
void getab(LL a,LL b,LL mod,LL k){for(LL i=2;i<k+2;i++){for(LL j=k+2-i;j<k+2;j++){A.m[i][j]=(A.m[i][j]%mod)*pow(a,j-(k+2-i),mod)%mod*pow(b,i-1-j+(k+2-i),mod);A.m[i][j]%=mod;}}
}
matrie multi(matrie a,matrie b,LL len,LL mod){matrie c;for(LL i=0;i<len;i++){for(LL j=0;j<len;j++){c.m[i][j]=0;for(LL k=0;k<len;k++){c.m[i][j]+=((a.m[i][k]%mod)*(b.m[k][j]%mod))%mod; //here ? noc.m[i][j]%=mod;}}}return c;
}
matrie quick_mod(LL n,LL len,LL mod)
{matrie res=I,temp=A;while(n){if(n&1) res=multi(res,temp,len,mod);temp=multi(temp,temp,len,mod);n>>=1;}return res;
}
LL quick(LL a,LL p,LL mod){LL res=1,temp=a%mod;while(p){if(p&1)res=res*temp%mod;temp=temp*temp%mod;p>>=1;}return res;
}
void init(){for(LL i=0;i<60;i++)for(LL j=0;j<60;j++)A.m[i][j]=0;
}
void show(int k){for(int i=0;i<k+2;i++){for(int j=0;j<k+2;j++)cout<<A.m[i][j]<<" ";cout<<endl;}
}
int main()
{LL t;cin>>t;LL f1,f2,a,b,k,n,m;for(LL i=0;i<60;i++) I.m[i][i]=1;while(t--){scanf("%lld %lld %lld %lld %lld %lld %lld",&f1,&f2,&a,&b,&k,&n,&m);if(k==0){printf("%lld\n",n%m);continue;}if(n==1){printf("%lld\n",quick(f1,k,m)); continue;}if(n==2){printf("%lld\n",(quick(f1,k,m)+quick(f2,k,m))%m);continue;}init();A.m[0][0]=A.m[0][k+1]=1;pascal(k);getab(a,b,m,k);A=quick_mod(n-1,k+2,m);LL ans=0;ans=(A.m[0][0]%m)*quick(f1,k,m)%m;for(LL i=1;i<k+2;i++){ans=ans+((A.m[0][i]%m)*pow(f2,i-1,m)%m*pow(f1,k-i+1,m))%m;ans=ans%m;}printf("%lld\n",ans);}return 0;
}
Problem D:A Simple Math Problem
#include<bits/stdc++.h>
typedef long long LL;
LL mod =10007;
using namespace std;
const int N=10;struct matrix
{LL m[N][N];
};
matrix mat;
matrix I;
matrix multi(matrix a,matrix b)
{matrix c;for(int i=0;i<N;i++)for(int j=0;j<N;j++){c.m[i][j]=0;for(int k=0;k<N;k++)c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;c.m[i][j]%=mod;}return c;
}
//矩阵快速幂
matrix power(matrix A,LL k)
{matrix ans=I,p=A;while(k){if(k&1) ans=multi(ans,p);k>>=1;p=multi(p,p);}return ans;
}
void init()
{for (int i=0;i<N;++i)scanf("%lld",&mat.m[0][i]);for (int i=1;i<N;++i){for (int j=0;j<N;++j){if (i==j+1)mat.m[i][j]=1;elsemat.m[i][j]=0;}}//初始化单位矩阵for(int i=0;i<N;i++)for(int j=0;j<N;j++)I.m[i][j]=(i==j)?1:0;
}int main()
{int k,m;while(~scanf("%d%d",&k,&m)){mod=m;init();if (k<10){printf("%lld\n",mat.m[0][k]%m);continue;}matrix temp=power(mat,k-9);LL ans=0;for (int i=0;i<N;++i){ans=(ans+temp.m[0][i]*(N-i-1))%m;ans%=m;}printf("%lld\n",ans);}return 0;
}
Problem E:Fibs之和
#include<bits/stdc++.h>
typedef long long LL;
const LL mod =1e9;
using namespace std;
struct matrix
{LL m[3][3];
};
matrix A={1,1,1,0,1,1,0,1,0};
matrix I={1,0,0,0,1,0,0,0,1};
//矩阵乘法
matrix multi(matrix a,matrix b)
{matrix c;for(int i=0;i<3;i++)for(int j=0;j<3;j++){c.m[i][j]=0;for(int k=0;k<3;k++)c.m[i][j]+=a.m[i][k]*b.m[k][j]%mod;c.m[i][j]%=mod;}return c;
}
//矩阵快速幂
matrix power(LL k)
{matrix ans=I,p=A;while(k){if(k&1) ans=multi(ans,p);k>>=1;p=multi(p,p);}return ans;
}
int main()
{LL a,b;while(scanf("%lld %lld",&a,&b)!=EOF){if(!a && !b) break;a--;LL s1,s2;if(a<0) s1=0;else if(a==0) s1=1;else{matrix ans=power(a-1);s1=(ans.m[0][0]*2%mod+ans.m[0][1]%mod+ans.m[0][2]%mod)%mod;}matrix ans=power(b-1);s2=(ans.m[0][0]*2%mod+ans.m[0][1]%mod+ans.m[0][2]%mod)%mod;LL l=((s2-s1)%mod+mod)%mod;cout<<l<<endl;}return 0;
}
Problem F:fibs的组合
//找规律就好了
#include<bits/stdc++.h>
using namespace std;int main()
{int n;while (cin >> n){ if (n % 3 == 0){cout << "yes" << endl;} else {cout << "no" << endl;}}return 0;
}
Problem G:fibs的位数
//公式
#include<bits/stdc++.h>
using namespace std;
int main()
{long long n,a,b,u,v;while(scanf("%lld %lld %lld %lld %lld",&n,&a,&b,&u,&v)!=EOF){double c=sqrt(u*u+4*v);double x=(u+c)/2.0;double y=(u-c)/2.0;double len=n*log10(x)+log10(b-a*y)-log10(c);printf("%lld\n",(long long)len+1);}return 0;
}
正文内容到此为止，希望大家都能有所收获