矩阵乘法
构造一个Fn=[fn,fn+1,sn,pn,...]的情况，然后看Fn=[fn,fn+1,sn,pn,...]*A=Fn+1=[fn+1,fn+2,sn+1,pn+1,...]，求出A矩阵，但是A矩阵不能包含变量n，然后求fn=f1*A^n次方来求，A^n次方因为矩阵满足结合率，则可以用矩阵快速幂来求即可
1.佳佳的斐波那契
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
这题要求的是Tn=f1+2f2+3f3...+nfn则可以构造一个Pn=n*Sn-Tn
则求Pn+1可以用Pn+Sn来求，最后Tn=n*Sn-Pn
则构造Fn=【fn,fn+1,Sn,Pn】
这个就是他们之间的关系：
求A矩阵有：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=4; int n,m; void mul(int c[][N],int a[][N],int b[][N])//c=a*b { static int temp[N][N];//创建个动态数组节省空间 memset(temp,0,sizeof temp); for(int i=0;i<N;i++)//矩阵乘法 for(int j=0;j<N;j++) for(int k=0;k<N;k++) temp[i][j]=(temp[i][j]+(ll)a[i][k]*b[k][j])%m; memcpy(c,temp,sizeof temp); } int main() { cin>>n>>m; int f1[N][N]={1,1,1,0};//构造的Fn的F1 int a[N][N]={ {0,1,0,0}, {1,1,1,0}, {0,0,1,1}, {0,0,0,1} };//求出来的A矩阵 int k=n-1; while(k)//求矩阵的A^n-1 { if(k&1) mul(f1,f1,a);//f1=f1*a mul(a,a,a);//a=a*a k>>=1; } int tn=((ll)n*f1[0][2]-f1[0][3])%m;//求Tn cout<<(tn+m)%m<<endl; return 0; }
2.GT 考试
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
跟状态机模型的设计密码特别像，只不过n的范围变大了
F[i]表示一维矩阵{f(i,0),f(i,1),f(i,2)....}
求前缀的最大匹配j用kmp来求
A矩阵的求法：假如如果我们的f(i,j)+某个字符c后可以转移到f（i+1,k）的话，则a[j][k]++;
只要这样做，算F[i]*A就会得到F[i+1]，F[i]表示一维矩阵{f(i,0),f(i,1),f(i,2)....}
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=25; int n,m,mod; char str[N]; int ne[N]; int a[N][N]; void mul(int c[][N],int a[][N],int b[][N])//c=a*b { static int t[N][N]; memset(t,0,sizeof t); for(int i=0;i<N;i++) for(int j=0;j<N;j++) for(int k=0;k<N;k++) t[i][j]=(t[i][j]+a[i][k]*b[k][j])%mod; memcpy(c,t,sizeof t); } int qmi(int k)//矩阵乘法快速幂 { int f0[N][N]={1};//初始状态 while(k) { if(k&1) mul(f0,f0,a);//f0=f0*a mul(a,a,a);//a=a*a k>>=1; } int res=0; for(int i=0;i<m;i++) res=(res+f0[0][i])%mod;//只要不等于m都符合条件 return res; } int main() { cin>>n>>m>>mod; cin>>str+1; for(int i=2,j=0;i<=m;i++)//求next过程 { while(j&&str[j+1]!=str[i]) j=ne[j]; if(str[j+1]==str[i]) j++; ne[i]=j; } for(int j=0;j<m;j++)//匹配过程 for(int c='0';c<='9';c++)//枚举字符0~9 { int k=j; while(k&&str[k+1]!=c) k=ne[k];//假如不匹配，则往前跳 if(str[k+1]==c) k++;//假如匹配了 if(k<m) a[j][k]++;//要小于匹配串，则这个位置的a[j][k]++，文字有说明 } cout<<qmi(n)<<endl; return 0; }
组合计数
1.牡牛和牝牛
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
我们可以认为母牛为0，公牛为1，则题目问的就是两个公牛之间至少得有k母牛，问方案数
我们可以用线性dp来做
假如i-k-1<0了，则之间让f(i)=f(0)，因为第i个位置有一头公牛也是满足条件
最终的答案就是f(0)+f(1)+f(2)+...f(n)这些都是合法方案，我们可以处理一个f(i)的前缀和，到时候更新状态时之间用就行，f(i)=s((i-k-1)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10,mod=5000011; int f[N],s[N];//s是f的前缀和 int n,k; int main() { cin>>n>>k; f[0]=s[0]=1;//初始化 for(int i=1;i<=n;i++)//状态计算 { f[i]=s[max(i-k-1,0)]; s[i]=(s[i-1]+f[i])%mod; } cout<<s[n]<<endl; return 0; }
2.方程的解
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
这题用隔板法来做，我们令n=x^xmod1000，则相当于把n分为k个整数，问方案数
相当于n个小球中间有n-1个隔，放k-1块版在他们隔板中，则中的方案数位C(n-1)(k-1)
但是C(n-1)(k-1)会很大的用高精度来做，至于求C(n)(k)用杨辉三角来求，C(n)(k)=C(n-1)(k)+C(n-1)(k-1)，则用高精度加法
至于高精度的位数大小开200足够了
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int M=1010,K=110,N=200; int f[M][K][N]; int k,x; int qmi(int a,int k,int p)//快速幂 { int res=1; while(k) { if(k&1) res=(ll)res*a%p; a=(ll)a*a%p; k>>=1; } return res; } void add(int c[],int a[],int b[])//高精度加法c=a+b { for(int i=0,t=0;i<N;i++) { t+=a[i]+b[i]; c[i]=t%10; t/=10; } } int main() { cin>>k>>x; int n=qmi(x,x,1000); //C(n-1,k-1) for(int i=0;i<n;i++) for(int j=0;j<=i&&j<k;j++) if(!j) f[i][j][0]=1;//C(i,0)=1 else add(f[i][j],f[i-1][j],f[i-1][j-1]);//f[i][j]=f[i-1][j]+f[i-1][j-1] int i=N-1; int *g=f[n-1][k-1]; while(!g[i]) i--;//取掉前导0 while(i>=0) cout<<g[i--];//输出答案 return 0; }
