k次操作 每次把每个格子中的值变为和他相邻不超过d的距离格子的和在%m
还是可以构造一个矩阵 那样例来说 5个格子的值为1 2 2 1 2
n m d k 为5 3 1 1
构造矩阵为
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
每次把这个矩阵左乘一次 1 2 2 1 2（竖着放）就相当于操作一次 k次操作可以做快速幂
然后矩阵相乘复杂度是你n^3 会超时
然后这是个循环矩阵 最右边那个数字放到最左边就是下一行 所以快速幂的时候做矩阵乘法的时候只需求第一行 下面的都可以根据第一行确定 复杂降为n^2
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 510;
struct matrix
{
long long a[maxn];
};
matrix A, B, C;
int n, m;
matrix matrix_get(matrix X, matrix Y)
{
//for(int i = 0; i < n; i++)
// printf("%d ", A.a[i]);
matrix Z;
memset(Z.a, 0, sizeof(Z.a));
/*for(int i = 2; i <= n; i++)
{
for(int j = 0; j < n; j++)
{
Y.a[i][j] = Y.a[1][(j-i+1+n)%n];
//printf("")
}
}*/
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
Z.a[i] += X.a[j] * Y.a[(j-i+n)%n];
Z.a[i] %= m;
}
}
return Z;
}
void matrix_pow(int k)
{
while(k)
{
if(k&1)
{
C = matrix_get(C, A);
}
A = matrix_get(A, A);
k >>= 1;
}
}
int main()
{
int d, k;
while(scanf("%d %d %d %d", &n, &m, &d, &k) != EOF)
{
for(int i = 0; i < n; i++)
scanf("%lld", &B.a[i]);
memset(A.a, 0, sizeof(A.a));
for(int i = 0; i < n; i++)
{
int dis = min(i, n-i);
if(dis <= d)
A.a[i] = 1;
}
memset(C.a, 0, sizeof(C.a));
C.a[0] = 1;
matrix_pow(k);
memset(A.a, 0, sizeof(A.a));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
A.a[i] += B.a[j] * C.a[(j-i+n)%n];
A.a[i] %= m;
}
}
printf("%d", A.a[0]);
for(int i = 1; i < n; i++)
printf(" %lld", A.a[i]);
printf("\n");
}
return 0;
}