FZU 1692 Key problem（循环矩阵优化 + 矩阵快速幂）

**链接：****传送门 **

题意：

n个小朋友围成一个环（ 2 <= n <= 100 ）然后进行m次的游戏。

一开始，第 i 个小朋友有 Ai 个苹果。

定义游戏的规则为：每一次游戏处于 i 位置的小朋友获得( L* A_(i+n-1)%n+R * A_(i+1)%n )个苹果（题目有误）

求 m 次游戏后每个小朋友的苹果数量。

思路：

一开始没有看到获得这两个字，gg，，也就是说 A_(i) = L* A_(i+n-1)%n+R * A_(i+1)+A_(i) ，那这道题与HDU 2276 Kiki & Little Kiki 2（ <-戳前面链接）就基本一模一样了，但是这道题如果不用循环矩阵优化就直接T掉了！

/*************************************************************************

    > File Name: fzu1692t3.cpp

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年05月04日 星期四 19时23分56秒

 ************************************************************************/

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int MOD;

const int maxn = 110;

#define ll long long

#define mod(x) ((x)%MOD)

#define cls(x) memset(x,0,sizeof(x))

struct mat{

	int m[maxn][maxn];

}unit;

int t,n,m,L,R;

void init_unit(){

	for(int i=0;i<maxn;i++)	unit.m[i][i] = 1;

}

// 利用循环矩阵降低复杂度

mat operator *(mat a,mat b){

	mat ret;

	cls(ret.m);				// 初始化一下以防出错

	for(int i=0;i<n;i++)

		for(int j=0;j<n;j++)

			ret.m[0][i] = mod( ret.m[0][i] + mod(a.m[0][j]*b.m[j][i]) );

	for(int i=1;i<n;i++)

		for(int j=0;j<n;j++)

			ret.m[i][j] = ret.m[i-1][(j-1+n)%n];

	return ret;

}

mat pow_mat(mat a,int x){

	mat ret = unit;

	while(x){

		if(x&1)	ret = ret*a;

		a = a*a;

		x >>= 1;

	}

	return ret;

}

mat a,b;

void init(){

	cls(a.m);

	for(int i=0;i<n;i++){

		a.m[i][ (i-1+n)%n ] = R;

		a.m[i][ i+1 ] = L;

		a.m[i][i] = 1;

	}

}

int main(){

	init_unit();

	int aa[maxn];

	cin>>t;

	while(t--){

		cin>>n>>m>>L>>R>>MOD;

		for(int i=0;i<n;i++)	scanf("%d",aa+i);

		init();

		mat ans = pow_mat(a,m);

		for(int i=0;i<n;i++){

			ll tmp = 0;

			for(int j=0;j<n;j++)

				tmp = mod(tmp + mod(ans.m[i][j]*aa[j]));

			ans.m[i][0] = tmp;

		}

		for(int i=0;i<n-1;i++)	printf("%d ",ans.m[i][0]);

		printf("%d\n",ans.m[n-1][0]);

	}

	return 0;

}

巴特西

FZU 1692 Key problem（循环矩阵优化 + 矩阵快速幂）

最新文章

热门文章

巴特西

FZU 1692 Key problem（ 循环矩阵优化 + 矩阵快速幂）

最新文章

热门文章

FZU 1692 Key problem（循环矩阵优化 + 矩阵快速幂）