poj 3150 Cellular Automaton

思路: 矩陣快速冪 分析: 1 題目給定n個數每個數在0～m-1之內，題目規定兩個數之間的距離為min(|i-j| , n-|i-j|)。現在給定d和k，表示做k次的變換，每一次變換過後每個數變成了一個新的數。這個新的數等於和它距離小於等於d的所有數的和%m 2 這題和之前做的兩道題很像hdu2276 和 FZU1692，都是屬於循環同構的問題    那麼我們先來看一下每個數在做一次變換過後變成什麼。因為要距離小於等於d，第一種|i-j| = d , 則j = i+d , 第二種情況n-|i-j| = d , 因此 j = n-d+i 。    第一個數等於 = num[1]+num[2]+....+num[d+1] + num[n-d+1]+...+num[n]    第二個數等於 = num[2]+....+num[d+2] + num[n-d+2]+...+num[n]    .............................................................................................................. 3 因為這裡的矩陣是循環同構的，因此我們只要求出第一行，剩下的我們就可以根據前一行推出。這樣就把矩陣的乘法的復雜度降到了O(n^2)   代碼:

 
/************************************************ 
 * By: chenguolin                               *  
 * Date: 2013-08-31                             * 
 * Address: http://blog.csdn.net/chenguolinblog * 
 ************************************************/  
#include<cstdio>  
#include<cstring>  
#include<iostream>  
#include<algorithm>  
using namespace std;  
  
typedef long long int64;  
const int N = 505;   
  
int n , MOD , d , k;  
int arr[N];  
  
struct Matrix{  
    int64 mat[N][N];  
    Matrix operator*(const Matrix &m)const{  
        Matrix tmp;  
        for(int i = 1 ; i <= n ; i++){  
            tmp.mat[1][i] = 0;  
            for(int j = 1 ; j <= n ; j++)  
                tmp.mat[1][i] += mat[1][j]*m.mat[j][i]%MOD;  
            tmp.mat[1][i] %= MOD;  
        }  
        for(int i = 2 ; i <= n ; i++){  
            tmp.mat[i][1] = tmp.mat[i-1][n];  
            for(int j = 2 ; j <= n ; j++)  
                tmp.mat[i][j] = tmp.mat[i-1][(j-1+n)%n];  
        }  
        return tmp;   
    }  
};  
  
void init(Matrix &m){  
    memset(m.mat , 0 , sizeof(m.mat));  
    for(int i = 1 ; i <= d+1 ; i++)  
        m.mat[1][i] = 1;  
    for(int i = n-d+1 ; i <= n ; i++)  
        m.mat[1][i] = 1;  
    for(int i = 2 ; i <= n ; i++){  
        m.mat[i][1] = m.mat[i-1][n];  
        for(int j = 2 ; j <= n ; j++)  
            m.mat[i][j] = m.mat[i-1][(j-1+n)%n];  
    }  
}  
  
void Pow(Matrix &m){  
    Matrix ans;  
    memset(ans.mat , 0 , sizeof(ans.mat));  
    for(int i = 1 ; i <= n ; i++)  
        ans.mat[i][i] = 1;  
    while(k){  
        if(k&1)  
            ans = ans*m;  
        k >>= 1;  
        m = m*m;  
    }  
    for(int i = 1 ; i <= n ; i++){  
        int64 sum = 0;  
        for(int j = 1 ; j <= n ; j++)  
            sum += ans.mat[i][j]*arr[j]%MOD;  
        if(i > 1) printf(" ");  
        printf("%lld" , sum%MOD);  
    }  
    puts("");  
}  
  
int main(){  
    Matrix m;  
    while(scanf("%d" , &n) != EOF){  
        scanf("%d%d%d" , &MOD , &d , &k);  
        for(int i = 1 ; i <= n ; i++)  
            scanf("%d" , &arr[i]);  
        init(m);  
        Pow(m);  
    }      
    return 0;  
}