POJ3150：Cellular Automaton

题意看不懂加题目想不通，很菜。

n<=500个数围城环，每次操作对每个数Ai把与i在环上相距不超过d<n/2（包括Ai）的数加起来取模m<=1e6，求K<=1e7次操作后的环。

存在递推关系，构造矩阵吧！比如样例一很丑。

于是矩阵快速幂，n*n*n*logK,很慢。

这个矩阵比较奇怪，每一行都是上一行右移一位，而且每一行和每一列长得一样。也就是说我们只保存第一行就能知道整个矩阵长什么样。

而我们的时间主要浪费在a的相乘上，所以a只维护一行，计算答案时把a还原，更新一行的“a”时亦然，具体见代码。

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #include<math.h>

 //#include<iostream>

 using namespace std;

 int n,mod,d,K;

 #define maxn 511

 int a[maxn],b[maxn];

 void mul(int *a,int *b,int *ans)

 {

     int t[maxn];

     memset(t,,sizeof(t));

     for (int i=;i<=n;i++)

         for (int j=;j<=n;j++)

             t[i]=(t[i]+1ll*a[j-i++(j-i>=?:n)]*b[j]%mod)%mod;

     for (int i=;i<=n;i++) ans[i]=t[i];

 }

 int main()

 {

     scanf("%d%d%d%d",&n,&mod,&d,&K);

     for (int i=;i<=n;i++) scanf("%d",&b[i]);

     memset(a,,sizeof(a));

     for (int i=;i<=d+;i++) a[i]=;

     for (int i=n;i>n-d;i--) a[i]=;

     while (K)

     {

         if (K&) mul(a,b,b);

         mul(a,a,a);

         K>>=;

     }

     for (int i=;i<=n;i++) printf("%d ",b[i]);

     return ;

 }

巴特西

POJ3150：Cellular Automaton

最新文章

热门文章