【样例输入二】
5 3 1 10
1 2 2 1 2
【样例输出二】
2 0 0 2 2
【数据范围】
<span ,"serif""> 对于30%的数据，n<=100,d<=100,k<=100 ；
对于60%的数据，n<=100 ；
对于100%的数据，1<=n<=500,1<=m<=1 000 000,0<=d<=n/2,1<=k<=10 000 000 。
solution
k是10^9，考虑矩阵乘法。
n是500，似乎会T。
有个高级的东西叫循环矩阵。
如果一个矩阵的下一行是由上一行左移得到，那么就可以用。
我们只记录第一行。
考虑c=a*b
c[1]=a[1][1]*b[1][1]+a[1][2]*b[2][1]+a[1][3]*b[3][1]+a[1][4]*b[4][1]
=a[1]*b[1]+a[2]*b[4]+a[3]*b[3]+a[4]*b[2]
c[2]=a[1][1]*b[1][2]+a[1][2]*b[2][2]+a[1][3]*b[3][2]+a[1][4]*b[4][2]
=a[1]*b[2]+a[2]*b[1]+a[3]*b[4]+a[4]*b[3]
c[(i+j-2)%n+1]=a[i]*b[j]
node operator *(node ax,node bx){
node c;c.cle();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
int x=(i+j-2)%n+1;
c.v[x]=(c.v[x]+ax.v[i]*bx.v[j])%mod;
}
return c;
}
//O(n^2)
还有一个性质：循环矩阵相乘还是循环矩阵。
这样就n^2解决了
