FZU 1692(Key problem)

spoiler posted @ 2011年4月28日 14:03 in 十个利用矩阵乘法解决的经典题目 , 1456 阅读

题目分析: 首先题目大意是,有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");
	}
}

 

Avatar_small
Katero 说:
2011年4月28日 19:08

想知道你用的编辑器或者IDE是?

Avatar_small
hello kity 说:
2011年4月28日 21:28

@Katero: 你是指我上面的代码格式么?这个是这种博客的附带编辑器哦
平时写代码 我用的是gedit就是Linux上的 嘿嘿

Avatar_small
Katero 说:
2011年4月28日 21:33

哦,这样啊。很不错,我不知道什么时候注册的这个博客了,不过,质量很高,看你的解题思路也很清晰,我都能看懂 哈哈

Avatar_small
hello kity 说:
2011年4月28日 23:43

@Katero: 谢谢啦 嘿嘿 谢谢您的赞美 我会更加努力的{^_^}


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter