FZU 1692 Key problem

点击打开FZU 1692

思路: 构造矩阵+矩阵快速幂

分析:

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;
}