这题递推式已经给了，就考虑怎么优化就可以了
对于a*b+c*d+e*f的形式直接拆到两个矩阵里即可
由于乘的时候实际是遍历每个项，所以不参与运算的设为0即可
码（from某知名选手）：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m,ta,tb,tc,mod; struct jz{ int p[99][99]; }a,b; jz operator *(const jz &x,const jz &y) { jz c; memset(c.p,0,sizeof(c.p)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) c.p[i][k]+=x.p[i][j]*y.p[j][k]; for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) c.p[i][j]%=mod; return c; } int main() { while (scanf("%d%d%d%d%d%d",&n,&mod,&ta,&tb,&tc,&m) && n){ int i; for (i=1; i<=n; i++) scanf("%d",&a.p[1][i]); memset(b.p,0,sizeof(b.p)); for (i=1; i<=n; i++){ if (i<n) b.p[i][i+1]=ta; b.p[i][i]=tb; if (i>1) b.p[i][i-1]=tc; } for (; m; m>>=1,b=b*b) if (m&1) a=a*b; for (i=1; i<=n; i++) printf("%d%c",a.p[1][i],(i<n)?' ':'\n'); } }