POJ 3233 Matrix Power Series （矩阵分块，递推）-白红宇

POJ 3233 Matrix Power Series （矩阵分块，递推）

阅读量：7042 次

发布时间：2019-06-28

本文共 1535 字，大约阅读时间需要 5 分钟。

矩阵乘法是可以分块的，而且幂的和也是具有线性的。

不难得到 S_i = S_i-1+A*A_i-1，A_i = A*A_i-1。然后矩阵快速幂就可以了。

/**********************************************************            ------------------                          **   author AbyssalFish                                   ***********************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;typedef long long ll;typedef vector
                  
                    row;typedef vector
                   
                     mat;int n, k, M;mat Mul;mat &operator *(mat &A, mat& B){ mat &R = Mul; R.assign(n,row(n)); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ for(int k = 0; k < n; k++){ R[i][j] = (R[i][j] +A[i][k]*B[k][j])%M; } } } return R;}//#define LOCAL#ifdef LOCALvoid censor(mat &B){ for(auto r: B){ for(int c: r) cout<
                    
                     <<' '; cout<
                     
                      >= 1; } return Re;}int main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif int nn; scanf("%d%d%d",&nn,&k,&M); n = 2*nn; mat A(nn,row(nn)); for(int i = 0; i < nn; i++){ for(int j = 0; j < nn; j++){ scanf("%d",&A[i][j]); } } mat B(n,row(n)); for(int i = 0; i < nn; i++) { B[i][i] = 1; copy(A[i].begin(),A[i].end(),B[i].begin()+nn); copy(A[i].begin(),A[i].end(),B[i+nn].begin()+nn); } B = B^k; for(int i = 0; i < nn; i++){ for(int j = 0; j < nn; j++){ printf("%d%c",B[i][j+nn],j==nn-1?'\n':' '); } }#ifdef LOCAL cout<<"rum time:"<
                      
                       <<"ms"<