POJ3150—Cellular Automaton（循环矩阵）

题目意思：有n个数围成一个环，现在有一种变换，将所有距离第i(1<=i<=n)个数小于等于d的数加起来，对m取余，现在要求将所有的数都变换k次，得到的n个数的值。

思路：构造一个循环矩阵，以下这个矩阵是以样例1为例的循环矩阵。

我们发现n尽然达到了500，复杂度是n^3logk，过不了，我们发现这个矩阵长得很奇葩，每一行都是上一行后移一位得到，所以我们每个矩阵可以n^2算出一行，然后通过平移得到全部的矩阵。从而把n^3的矩阵乘法变成n^2，复杂度是n^2logk，就可以AC了，其他没有什么奇怪的操作。第一道循环矩阵题，算是涨姿势了，循环矩阵乘法模板记住了。

代码：

 //Author: xiaowuga

 #include<iostream>

 #include<cstring>

 #define maxx INT_MAX

 #define minn INT_MIN

 #define inf 0x3f3f3f3f

 #define N  505

 using namespace std;

 long long MOD;

 typedef long long ll;

 long long  n,size;//第n项，矩阵大小

  long long f[];

 struct Matrix{

     long long mat[N][N];

     void clear(){

         memset(mat,,sizeof(mat));

     }

     Matrix operator * (const Matrix & m) const{

         Matrix tmp;

         tmp.clear();

         for(int i=;i<size;i++){

             for(int j=;j<size;j++){

                 tmp.mat[][i]+=mat[][j]*m.mat[j][i]%MOD;

             }

             tmp.mat[][i]%=MOD;

         }

         for(int i=;i<size;i++){

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

                 tmp.mat[i][j]=tmp.mat[i-][(j+size-)%size];

         }

         return tmp;

     }

 }M,ANS;

 Matrix ans;

 void POW(Matrix m,ll k){

     memset(ans.mat,,sizeof(ans.mat));

     for(int i=;i<size;i++) ans.mat[i][i]=;

     while(k){

         if(k&) ans=ans*m;

         k/=;

         m=m*m;

     }

      long long sum;

         for(int i=;i<size;i++){

             sum=;

             for(int j=;j<size;j++){

                 sum+=ans.mat[i][j]*f[j]%MOD;

             }

             if(i==) cout<<sum%MOD;

             else cout<<" "<<sum%MOD;

         }

         cout<<endl;

 }

 int main() {

     ios::sync_with_stdio(false);cin.tie();

     long long d;

     while(cin>>size>>MOD>>d>>n){

         M.clear();

         for(int i=;i<size;i++) cin>>f[i];

         for(int i=;i<size;i++){

             M.mat[i][i]=;

             for(int j=;j<=d;j++){

                 M.mat[i][(i+j+size)%size]=;

                 M.mat[i][(i-j+size)%size]=;

             }

         }

         for(int i=;i<size;i++){

             for(int j=;j<size;j++) cout<<M.mat[i][j]<<' ';

             cout<<endl;

         }

         POW(M,n);

     }

     return ;

 }

巴特西

POJ3150—Cellular Automaton（循环矩阵）

最新文章

热门文章