记录编号	550029	评测结果	AAAAAAAAAA
题目名称	[UVa 1386] 细胞自动机	最终得分	100
用户昵称	ZooxTark➲	是否通过	通过
代码语言	C++	运行时间	0.631 s
提交时间	2020-03-01 16:11:20	内存使用	13.67 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n,m,d,k;
long long matrix[505],ans[505],c[510];

void Multi(long long a[],long long b[])
{
    memset(c,0,sizeof(c));
    for(int i = 0;i < n;i++)
        for(int j = 0;j < n;j++)
            c[i] += a[j] * b[(i - j + n) % n];
    for(int i = 0;i < n;i++)
    {
        a[i] = c[i] % m;
    }
}

int main()
{
    freopen("cellularautomaton.in","r",stdin);
    freopen("cellularautomaton.out","w",stdout);
    ios::sync_with_stdio(false);
    while(cin >> n >> m >> d >> k)
    {
        memset(matrix,0,sizeof(matrix));
        memset(ans,0,sizeof(ans));
        for(int i = 0;i < n;i++)
        {
            cin >> ans[i];
        }
        matrix[0] = 1;
        for(int i = 1;i <= d;i++)
        {
            matrix[i] = matrix[n - i] = 1;
        }
        while(k)
        {
            if(k & 1)
                Multi(ans,matrix);
            Multi(matrix,matrix);
            k >>= 1;
        }
        for(int i = 0;i < n;i++)
        {
            cout << ans[i] << " ";
        }
        cout << endl;
    }
    return 0;
}