前言
如果有不清楚矩阵乘法的，可以加QQ了解一下：3099895260
如果会的话可以跳过这个步骤
就是我们设两个矩阵为\(a\),\(b\)。他们两个可以乘在一起当且仅当第一个矩阵为\(n*p\)且第二个矩阵\(p*m\)，他们乘起来的结果是\(c\)矩阵，\(n*m\)
然后乘法就是这样子实现的.
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=p;k++) c[i][j]=a[i][k]*b[k][j];
然后如果有多个同样子的矩阵乘在一起，就可以像普通乘法快速幂。
正话
矩阵快速幂的板子基本上是没有用的，真正在题目中出现的还是矩阵加速。
我们先来看一道题目：
这显然是递推对吧，但是因为\(n<=2*10^9\)十分无奈，所以考虑优化。
我们来深层次挖掘一下他的式子：
\(a_i=a_{i-1}+a_{i-3}(i>3)\)
这个东西有什么用呢？
我们令一个矩阵为\(S\{3*1\}={a_i,a_{i-1},a_{i-2}}\)
那么如果我们要递推呢？
如何转移到\(a_{i+1},a_i,a_{i-1}\)呢？
再令一个矩阵\(T\{3*3\}\)表示一个转移矩阵，那么根据递推式子和矩阵乘法的原则，有一个这样子的矩阵？
\(T[3][3]={1,1,0},{0,0,1},{1,0,0}\)这个可能竖着比较好看。
\(\{1,1,0\}\)
\(\{0,0,1\}\)
\(\{1,0,0\}\)
那么就是每一列对应着对应位置的转移，大致推导就是这样。
那么考虑简化这个东西。
\(Ans=(((S*T)*T)*T)\)
那么可以把括号拆开，就可以得出\(Ans=S*T^k\)
所以可以矩阵快速幂优化就可以AC！！！
#include#include #include #include #include #include #define ll long long#define re registerinline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const ll Mod=1e9+7;struct matrix{ ll a[3][3]; matrix operator*(const matrix b)const{ matrix c; for(re int i=0;i<3;i++) for(re int j=0;j<3;j++){ c.a[i][j]=0; for(re int k=0;k<3;k++) c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%Mod)%Mod; } return c; }}S,T;void init(){ S.a[0][0]=S.a[0][1]=S.a[0][2]=1; T.a[0][0]=T.a[0][1]=T.a[2][0]=1; T.a[1][1]=T.a[1][0]=T.a[0][2]=T.a[2][1]=T.a[2][2]=0; T.a[1][2]=1; }int n;int main(){ int t=gi(); while(t--){ n=gi(); if(n<=2){ puts("1");continue; } init(); n-=3; while(n){ if(n&1)S=S*T; T=T*T;n>>=1; } printf("%lld\n",S.a[0][0]); } return 0;}