矩阵快速幂。
样例是这样构造矩阵的：
矩阵很好构造，但是500*500*500*logk的复杂度显然是无法通过这题的。
其实本题构造出来的矩阵是一个循环矩阵，只需直到第一行或者第一列，即可直到整个矩阵是怎么样的。
所以，中间计算的时候，需要直到第一行是什么即可，即1*n的矩阵乘n*n的矩阵。时间复杂度o(n*n*logk)
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std; const int maxn=+;
int n,d,k;
long long mod;
long long z[maxn],a[maxn];
long long y[maxn],x[maxn];
long long tmp[maxn][maxn];
long long r[maxn]; void init()
{
memset(y,,sizeof y);
y[]=;
memset(x,,sizeof x);
x[]=;
for(int i=; i<=+d; i++) x[i]=;
for(int i=n; i>=n-d+; i--)x[i]=;
} int main()
{
while(~scanf("%d%lld%d%d",&n,&mod,&d,&k))
{
for(int i=; i<=n; i++) scanf("%lld",&z[i]);
init();
while(k)
{
for(int i=; i<=n; i++)
{
int tot=;
for(int j=i; j<=n; j++) tmp[i][j]=x[tot++];
for(int j=; j<=i-; j++) tmp[i][j]=x[tot++];
} if(k%==)
{
for(int j=; j<=n; j++)
{
long long sum=;
for(int t=; t<=n; t++) sum=(sum+(y[t]*tmp[j][t])%mod)%mod;
r[j]=sum;
} for(int j=; j<=n; j++) y[j]=r[j]; k--;
}
else if(k%==)
{
for(int j=; j<=n; j++)
{
long long sum=;
for(int t=; t<=n; t++) sum=(sum+(x[t]*tmp[j][t])%mod)%mod;
r[j]=sum;
}
for(int j=; j<=n; j++) x[j]=r[j]; k=k/;
}
} for(int i=; i<=n; i++)
{
int tot=;
for(int j=i; j<=n; j++) tmp[i][j]=y[tot++];
for(int j=; j<=i-; j++) tmp[i][j]=y[tot++];
} for(int j=; j<=n; j++)
{
long long sum=;
for(int t=; t<=n; t++) sum=(sum+(z[t]*tmp[j][t])%mod)%mod;
r[j]=sum;
} for(int j=; j<=n; j++)
{
printf("%d",r[j]);
if(j<n) printf(" ");
else printf("\n");
}
}
return ;
}