FZU 1692 Key problem

思路: 構造矩陣+矩陣快速冪 分析: 1 題目的意思是有n個人構成一個圈，每個人初始的有ai個蘋果，現在做m次的游戲，每一次游戲過後第i個人能夠增加R*A(i+n-1)%n+L*A(i+1)%n 個蘋果（題目有錯），問m輪游戲過後每個人的蘋果數 2 根據題目的意思我們能夠列出一輪過後每個人的蘋果數    a0 = a0+R*an-1+L*a1    a1 = a1+R*a0+L*a2    .............................    an-1 = an-1+R*an-2+L*a0 3 根據第二條思路我們可以構造出如下的矩陣    1 L 0 ...... R        a0         a0'    R 1 L .........  *     a1         a1'    ...................       ....      = ......     ...........R 1 L      an-2       an-2'    L ...........R 1      an-1       an-1' 4 那麼根據3我們可以利用矩陣快速冪求出最後的答案，但是題目的n最大為100，m最大為10^9，那麼每個case的時間復雜度為O(Logm*n^3)，當n最大為100的時候是會TLE的 5 我們發現初始的矩陣裡面，矩陣是一個循環同構的，就是說矩陣的每一行度能夠從上一行推出，那麼我們只要利用O(n^2)的時間求出第一行，然後我們在利用遞推求出剩下的n-1行，那麼總的時間復雜度為O(Logm*n^2)   代碼:

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