[LA-3704] Cellular Automaton 细胞自动机

题面

样例

Sample Input
5 3 1 1
1 2 2 1 2
5 3 1 10
1 2 2 1 2
Sample Output
2 2 2 2 1
2 0 0 2 2

思路

既然这里讲的是矩阵的运算那么一定是要构造一个递推的关系
从题面上很难发现有什么规律可言
于是
我们动手画画
发现每次的变化都是上次的有序排列
比如样例中的第一组输入输出
[1 1 0 0 1] [1] = [2]
[1 1 1 0 0] [2] = [2]
[0 1 1 1 0] [2] = [2]
[0 0 1 1 1] [1] = [2]
[1 0 0 1 1] [2] = [1]
发现了么，左边的矩阵的每下一行都是上一行的元素向右移动一格
这样的矩阵只要保存一行信息即可我们称之为”循环矩阵”.
于是原来n^3logk的爆炸事件在这个循环矩阵的优化下
降到了n^2logk.

代码

#include<bits/stdc++.h>
using namespace std;  
#define INF 0x3f3f3f3f  
const long long N=505;  
typedef long long ll;  
  
typedef struct {  
    ll mat[N];  
}Mat;  
  
int n,d,m,k;  
  
Mat multi(Mat a,Mat b) {  
    Mat c;  
    memset(c.mat, 0, sizeof(c.mat));  
    for (int i=1; i<=n; i++) {  
        for (int j=1; j<=n; j++) {  
            c.mat[i]+=a.mat[j]*b.mat[(i-j+n)%n+1];  
            c.mat[i]%=m;  
        }  
    }  
    return c;  
}  
  
Mat qui(Mat a,int b) {  
    Mat c;  
    memset(c.mat, 0, sizeof(c.mat));     
    c.mat[1]=1;  
    while (b) {  
        if (b&1) {  
            c=multi(c, a);  
        }  
        a=multi(a, a);  
        b>>=1;  
    }  
    return c;  
}  
int main(int argc, char *argv[]) 
{  
    int f[N];  
    Mat A;  
    while (cin>>n>>m>>d>>k) {  
        memset(f, 0, sizeof(f));  
        for (int i=1; i<=n; i++) {  
            scanf("%d",&f[i]);  
        }  
        memset(A.mat, 0, sizeof(A.mat));  
          
        for (int i=1; i<=1; i++) {  
            A.mat[i]=1;  
            for (int j=1; j<=d; j++) {  
                A.mat[(i-1+j)%n+1]=1;  
                A.mat[(i-1-j+n)%n+1]=1;  
            }  
        }  
        A=qui(A, k);  
        ll res[N];  
        memset(res, 0, sizeof(res));  
        for (int i=1; i<=n; i++) {  
            for (int j=1; j<=n; j++) {  
                res[i]+=A.mat[(i-j+n)%n+1]*f[j];  
                res[i]%=m;  
            }  
        }  
        for (int i=1; i<n; i++) {  
            printf("%lld ",res[i]);  
        }  
        printf("%lld\n",res[n]) ;
    }  
    return 0;  
}