思路: 构造矩阵+矩阵快速幂
分析:
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; }