FZU 1692(Key problem)

题目分析： 首先题目大意是，有n个小孩，初始时每个人有ai个苹果。现在要进行m轮游戏。每进行一轮游戏，第i个小孩的苹果增加

( R*A_(i+n-1)%n+L*A_(i+1)%n )个，求进行m轮游戏后，每个小孩有多少个苹果。（0<=m<=10^9,结果模M后输出，1<=M<=10^6）！注意原题目的公式是错的，害的我郁闷了好久～真的 faint！

思路分析：

这些都属于 循环同构的矩阵 计算的一个巧妙的算法就是，只算第一行，然后接下来的只要平移一个单位到下面，然后复制！

做这种题目还是要首先构造出一个矩阵 模拟他的递归过程！

我这里构造的矩阵是：

1 L ....  R

R 1 L..  0

0 R 1 L..0

L..... 0 R 1

然后递归多少次，我只要把这个矩阵乘多少次就可以了，这样做的高效远远优于递归的!

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct M{
	int s[101][101];
};
int n,p,t;
struct M tempt,unit,res;
//计算矩阵的幂的时候，因为我要计算的矩阵是 循环同构的
//所以只需要计算第一行，其他的N-1行只需要帮他上面一行的
//结果平移一个单位，然后再复制下来就OK啦！
struct M multiply(struct M a,struct M b){
	struct M c;
	int i,j,k;
	for(i=1;i<=1;i++)
		for(j=1;j<=n;j++){
			c.s[i][j]=0;
			for(k=1;k<=n;k++){
				if(a.s[i][k]&&b.s[k][j])
					c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%p)%p;
			}	
		}
	for(i=2;i<=n;i++){
		c.s[i][1]=c.s[i-1][n];
		for(j=2;j<=n;j++)
			c.s[i][j]=c.s[i-1][j-1];
	}
	return c;
}
struct M multiply2(struct M a,struct M b){
	struct M c;
	int i,j,k;
	for(i=1;i<=n;i++)
		for(j=1;j<=1;j++){
			c.s[i][j]=0;
			for(k=1;k<=n;k++){
				if(a.s[i][k]&&b.s[k][j])
					c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%p)%p;
			}	
		}
	return c;
}

void paw(){
	struct M ans=unit;
	int i,j;
	struct M a=tempt;
	while(t){
		if(t%2==1)
			ans=multiply(ans,a);					
		a=multiply(a,a);
		t/=2;
	}
	res=multiply2(ans,res);
}
int main(){
	int cas,l,r,i,j;
	int sim[102];
	memset(unit.s,0,sizeof(unit.s));
	for(i=1;i<=100;i++)
		unit.s[i][i]=1;
	cin>>cas;
	while(cas--){
		memset(res.s,0,sizeof(res.s));
		memset(tempt.s,0,sizeof(tempt.s));
		scanf("%d %d %d %d %d",&n,&t,&r,&l,&p);
		for(i=1;i<=n;i++)
			scanf("%d",∼[i]);
		for(j=1,i=n;i>=1;j++,i--){
			res.s[j][1]=sim[i];
		}
		tempt.s[1][1]=1;	tempt.s[1][2]=l;
		tempt.s[1][n]=r;
		for(i=2;i<=n;i++){
			tempt.s[i][1]=tempt.s[i-1][n];
			for(j=2;j<=n;j++)
				tempt.s[i][j]=tempt.s[i-1][j-1];
		}
		paw();
		for(i=n;i>1;i--)
			printf("%d ",res.s[i][1]);
		printf("%d",res.s[i][1]);
		printf("\n\n");
	}
}