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

/*
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long int64;
int n,m,d,k;
struct tagMat
{
    int64 e[501];
    tagMat operator * (const tagMat& b)
    {
        tagMat c;
        memset(c.e,0,sizeof(c.e));
        for(int i = 0;i < n;++i)
            for(int j = 0;j < n;++j)
                c.e[i] = (c.e[i] + e[j] * b.e[(i - j + n) % n] % m) % m;
        return c;
    }
    tagMat operator *= (const tagMat& b)
    {
        *this = *this * b;
    }
}M1,M2;

int main()
{
    freopen("cellularautomaton.in","r",stdin);
    freopen("cellularautomaton.out","w",stdout);
    ios::sync_with_stdio(false);
    while(cin >> n >> m >> d >> k)
    {
        memset(M1.e,0,sizeof(M1.e));
        memset(M2.e,0,sizeof(M2.e));
        for(int i = 0;i < n;++i)
        {
            cin >> M2.e[i];
        }
        for(int i = 0;i <= d;++i)
        {
            M1.e[i] = 1;
        }
        for(int i = n - 1;i >= n - d;--i)
        {
            M1.e[i]=1;
        }
        while(k > 0)
        {
            if(k & 1)
                M2 *= M1;
            M1 *= M1;
            k >>= 1;
        }
        for(int i = 0;i < n;++i)
        {
            cout << M2.e[i] << " ";
        }
        cout << "\n";
    }
    return 0;
}
*/
#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;
}