POJ 3150 Cellular Automaton 矩阵dp

http://poj.org/problem?id=3150

思路：利用矩阵A，B具有A[i][j]=A[i-1][j-1],B[i][j]=B[i-1][j-1]（i-1<0则表示i-1+n,j-1<0则表示j-1+n）
我们可以得出矩阵C=A*B也具有这个性质
C[i][j]=sum(A[i][t]*B[t][j])=sum(A[i-1][t-1],B[t-1][j-1])=sum(A[i-1][t],B[t][j-1])=C[i-1][j-1]
也就是说我们知道了矩阵C的某一行，就可以知道所有行，所以我们对每个矩阵保存其第一行即可
矩阵的每一个元素也可得知C[i][j]=C[0][j-i] (j-i<0时j-i表示j-i+n)
这样每次我们求C=A*B只要求c[j]=C[0][j]=sum(A[0][t]*B[t][j])=sum(a[t]*b[t-j]).
只求一行这样复杂度就降下来了。

代码：

#include<stdio.h>
#include<string.h>
__int64 N ,M ,D ,K ;
__int64 start[510] ;
__int64 m[510] ;
__int64 c[510] ;
__int64 res[510] ;
void cal(__int64 A[] , __int64 B[]){
for(int i=0;i<N;i++){
c[i] = 0 ;
for(int t=0;t<N;t++){
c[i] += A[t]*B[(N-t+i)%N] ;
}
}
for(int i=0;i<N;i++)
A[i] = c[i]%M ;
}
void solve(){
while(K){
if(K&1)	cal(res , m);
cal(m,m);
K >>= 1;
}
for(int i=0;i<N;i++){
c[i] = 0 ;
for(int t=0;t<N;t++){
c[i] += res[(N+t-i)%N]*start[t] ;
}
c[i] %= M ;
}
}
int main(){
while(scanf("%I64d%I64d%I64d%I64d",&N,&M,&D,&K) == 4){
for(int i=0;i<N;i++)
scanf("%I64d",&start[i]);
memset(res, 0, sizeof(res));
memset(m , 0 ,sizeof(m));
m[0] = 1 ; res[0] = 1 ;
for(int i=1;i<=D;i++){
m[i] = m[N-i] = 1 ;
}
solve();
for(int i=0;i<N;i++){
printf("%I64d%c",c[i],i==N-1?'n':' ');
}
}
return 0 ;
}

最后

以上就是精明紫菜为你收集整理的POJ 3150 Cellular Automaton 矩阵dp的全部内容，希望文章能够帮你解决POJ 3150 Cellular Automaton 矩阵dp所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。