poj3735(矩阵快速幂)

231 阅读 0 评论 153 点赞

我是靠谱客的博主超级荷花，这篇文章主要介绍poj3735(矩阵快速幂)，现在分享给大家，希望可以做个参考。

Training little cats

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 14625		Accepted: 3619

Description

Facer's pet cat just gave birth to a brood of little cats. Having considered the health of those lovely cats, Facer decides to make the cats to do some exercises. Facer has well designed a set of moves for his cats. He is now asking you to supervise the cats to do his exercises. Facer's great exercise for cats contains three different moves:
g i : Let the ith cat take a peanut.
e i : Let the ith cat eat all peanuts it have.
s i j : Let the ith cat and jth cat exchange their peanuts.
All the cats perform a sequence of these moves and must repeat it m times! Poor cats! Only Facer can come up with such embarrassing idea.
You have to determine the final number of peanuts each cat have, and directly give them the exact quantity in order to save them.

Input

The input file consists of multiple test cases, ending with three zeroes "0 0 0". For each test case, three integers n, m and k are given firstly, where n is the number of cats and k is the length of the move sequence. The following k lines describe the sequence.
(m≤1,000,000,000, n≤100, k≤100)

Output

For each test case, output n numbers in a single line, representing the numbers of peanuts the cats have.

Sample Input

Sample Output

2 0 1

题意：有n只猫一开始他们的值都是0，有三种操作，第i只猫值加1，第i只猫值变为0，dii只猫和第j只猫值交换，这样的操作选择几组，重复m次，求出最后每只猫的值。

思路：矩阵快速幂，就是建矩阵比较难，参考：http://blog.csdn.net/u013068502/article/details/38355621

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define ll long long
int n,m,k;
struct mat
{
	ll a[105][105];     //a[i][n]存放第i只猫有的豆子数 
};
mat mat_mul(mat x,mat y)  //矩阵相乘 
{  
    mat res;  
    memset(res.a,0,sizeof(res.a));  
    for(int i=0;i<=n;i++)  
        for(int j=0;j<=n;j++)  
        {
        	if(x.a[i][j])       //优化，判断这个点是否为0 
        	{
        		for(int k=0;k<=n;k++)
        		{
        			res.a[i][k]+=(x.a[i][j]*y.a[j][k]);
				}
			}
		}
    return res;  
}  
void solve()
{
	mat op,op0;
	memset(op.a,0,sizeof(op.a));
	for(int i=0;i<=n;i++)op.a[i][i]=1;
	op0=op;
	char s[2];
	int x,y;
	//先把做一次后的结果矩阵找出来 
	for(int i=0;i<k;i++)
	{
		scanf("%s",s);
		mat op1=op;
		if(s[0]=='g')
		{
			scanf("%d",&x);
			op1.a[x-1][n]=1;
		}
		else if(s[0]=='e')
		{
			scanf("%d",&x);
			op1.a[x-1][x-1]=0;
		}
		else if(s[0]=='s')
		{
			scanf("%d%d",&x,&y);
			op1.a[x-1][x-1]=0;
			op1.a[x-1][y-1]=1;
			op1.a[y-1][y-1]=0;
			op1.a[y-1][x-1]=1;
		}
		op0=mat_mul(op1,op0);
	}
	//矩阵快速幂 
	while(m)
	{
		if(m&1)op=mat_mul(op0,op);
		op0=mat_mul(op0,op0);
		m>>=1;
	}
	for(int i=0;i<n-1;i++)printf("%lld ",op.a[i][n]);
	printf("%lldn",op.a[n-1][n]);
}
int main()
{
	while(~scanf("%d%d%d",&n,&m,&k)&&(n||m||k))
	{
		solve();
	}
}