POJ 3150 Cellular Automaton（矩阵快速幂+特殊矩阵的性质）

题目的意思开始没看懂，看了别人的博客的翻译

题目大意：一个元胞中包含若干细胞，每个细胞都有初始value值，题目定义了一个细胞距离，细胞i、j之间的距离d=min(|i-j|,n-|i-j|)，称
与细胞i距离不超过d的所有细胞（包括该细胞本身）的集合为细胞i的d-environment，经过一个d-steps变换后，元胞中每一个细胞的值变
为该细胞d-environment内所有细胞value值总和模上m，最后求经过k个d-steps变换后，元胞中每个细胞的最终值。

思路：

可以用矩阵相乘来表示这种step变化，每次变化乘上的矩阵是A：（比如d=1）

[1, 1, 0, 0, 1]
[1, 1, 1, 0, 0]
[0, 1, 1, 1, 0]
[0, 0, 1, 1, 1]
[1, 0, 0, 1, 1]

所以A^k求出以后再乘上细胞的value矩阵便可

不过仅仅是这样还会超时，必须利用这个矩阵的性质

比如A^3=

[7, 6, 4, 4, 6]
[6, 7, 6, 4, 4]
[4, 6, 7, 6, 4]
[4, 4, 6, 7, 6]
[6, 4, 4, 6, 7]

任然具有每行错开一位的性质，可以证明始终有这种性质

所以只需求出第一行便可，复杂度从n^3降到n^2

//8132K	3532MS
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
int n,mod,d,k;
struct mat{
int a[505][505];
void ini(){
memset(a,0,sizeof(a));
}
};
mat cell,step,ans,tans;
mat mul(mat &m1,mat &m2){
mat ans;
ans.ini();
for(int j=1;j<=n;j++)
if(m1.a[1][j])
for(int k=1;k<=n;k++)
ans.a[1][k]=((ll)ans.a[1][k]+(ll)m1.a[1][j]*(ll)m2.a[j][k])%(ll)mod;
for(int i=2;i<=n;i++)
for(int j=1;j<=n;j++)
ans.a[i][j]=ans.a[1][(n+j-i)%n+1];
return ans;
}
void print(mat &m){ //debug
puts("");
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
printf("%d%c",m.a[i][j],j==n?'n':' ');
}
int main(){
scanf("%d%d%d%d",&n,&mod,&d,&k);
for(int i=1;i<=n;i++)
scanf("%d",&cell.a[i][1]);
for(int i=1;abs(i-1)<=d;i++){
step.a[1][i]=1;
step.a[1][(n-i+1)%n+1]=1;
}
for(int i=2;i<=n;i++)
for(int j=1;j<=n;j++)
step.a[i][j]=step.a[1][(n+j-i)%n+1];
for(int i=1;i<=n;i++)
tans.a[i][i]=1;
while(k){
if(k&1) tans=mul(tans,step);
step=mul(step,step);
k>>=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(tans.a[i][j])
ans.a[i][1]=((ll)ans.a[i][1]+(ll)tans.a[i][j]*(ll)cell.a[j][1])%(ll)mod;
for(int i=1;i<=n;i++)
printf("%d%c",ans.a[i][1],i==n? 'n':' ');
return 0;
}

最后

以上就是香蕉哈密瓜为你收集整理的POJ 3150 Cellular Automaton（矩阵快速幂+特殊矩阵的性质）的全部内容，希望文章能够帮你解决POJ 3150 Cellular Automaton（矩阵快速幂+特殊矩阵的性质）所遇到的程序开发问题。

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