FZU 1692 Key problem（構造矩陣+矩陣快速冪）

FZU 1692 Key problem（構造矩陣+矩陣快速冪）

【題意】：1 題目的意思是有n個人構成一個圈，每個人初始的有ai個蘋果，現在做m次的游戲，每一次游戲過後第i個人能夠增加R*A_(i+n-1)%n+L*A_{(i+1)%n 個蘋果（題目有錯），問m輪游戲過後每個人的蘋果數}

_{【思路】：}

_{根據題目的意思我們能夠列出一輪過後每個人的蘋果數}

_{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)}

代碼：

/*
Problem id. FZU 1692
RunID: 631373
UserID: ACM_herongwei
Submit time: 2015-09-04 11:58:16
Language: C++
Length: 1806 Bytes.
Result: Accepted
*/

#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
const int N=105;

int arr[N];
int n,m,L,R,MOD;

struct mut
{
    LL mat[N][N];
    mut()
    {
        memset(mat,0,sizeof(mat));
    }
    void init()
    {
        for(int i=0; i>=1;
    }
    return unit;
}

void solve()
{
    int ans=0;
    mut unit,a;
    scanf(%d %d %d %d %d,&n,&m,&R,&L,&MOD);
    for(int i=0; i