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; }