http://vjudge.net/problem/POJ-3150 题解
比较好推出转移矩阵： 1 1 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 但是矩阵相乘500*500*500*log(k)还是会超时 可以观察这个转移矩阵，其实只知道第一行就可以推出每行，每列，所以保留第一行作为转移矩阵，这样就从N^3变成了N^2。
#include<stdio.h> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long ll; ll n,m,d,k,mtr[505],res[505]; void mul(ll a[],ll b[]) { ll t[505]; memset(t,0,sizeof(t)); for(int i=0;i<n;i++) // if(a[i]) for(int k=n+i,j=0;j<n;k--,j++) { int z=k%n; // cout<<z<<endl; t[i]=t[i]+a[j]*b[z]; t[i]%=m; } for(int i=0;i<n;i++) a[i]=t[i]; } int main() { while(cin>>n>>m>>d>>k) { memset(mtr,0,sizeof(mtr)); for(int i=0;i<n;i++) scanf("%d",&res[i]); for(int i=0;i<=d;i++) mtr[i]=1; for(int i=n-1;i>=n-d;i--) mtr[i]=1; ll ans[505]; memset(ans,0,sizeof(ans)); ans[0]=1; while(k) { if(k&1) mul(ans,mtr); k>>=1; mul(mtr,mtr); } mul(res,ans); for(int i=0;i<n;i++) printf(i==n-1?"%d\n":"%d ",res[i]); } }