UVa 3704 Cellular Automaton（矩乘）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 const int N = 500+10;
 8 
 9 int m,n,d,k;
10 
11 void mul(LL a[],LL b[]) {
12     LL c[N];
13     for(int i=0;i<n;i++) {
14         c[i]=0;
15         for(int j=0;j<n;j++)
16             c[i]=(c[i]+a[j]*b[(i-j+n)%n])%m;
17     }
18     memcpy(a,c,sizeof(c));
19 }
20 LL ans[N],tmp[N],A[N];
21 
22 void pow(int p) {
23     memset(ans,0,sizeof(ans));
24     memset(tmp,0,sizeof(tmp));
25     for(int i=-d;i<d+1;i++) {
26         tmp[(i+n)%n]=1;
27     }
28     ans[0]=1;
29     while(p) {
30         if(p&1) mul(ans,tmp);
31         mul(tmp,tmp);
32         p>>=1;
33     }
34 }
35 
36 int main() {
37     while(scanf("%d%d%d%d",&n,&m,&d,&k)==4) {
38         pow(k);
39         for(int i=0;i<n;i++) scanf("%d",&A[i]);
40         mul(ans,A);
41         printf("%lld",ans[0]);
42         for(int i=1;i<n;i++) printf(" %lld",ans[i]);
43         putchar(‘\n‘);
44     }
45     return 0;
46 }