poj 3735 Training little cats 矩阵的幂

题意：

给一个长度为n的数列，初始化为0，有3种操作：1）将某个元素增加1;2）将某个元素置0；3)交换两个元素。现在给出包含k个操作的一组操作，求m组操作后数列的状态。

分析：

找出初始矩阵A和转移矩阵T后就可以用快速幂计算了。

代码：

//poj 3735
//sep9
#include <iostream>
using namespace std;
typedef long long LL;
const int maxN=128;
int n,m,k;
struct Matrix
{
	LL a[maxN][maxN];
	void init(){
		memset(a,0,sizeof(a));	
		for(int i=0;i<=n;++i)
			a[i][i]=1;
	}		
}A,T;

Matrix operator *(Matrix x,Matrix y)
{
	Matrix tmp;
	memset(tmp.a,0,sizeof(tmp.a));
	for(int i=0;i<=n;++i)	
		for(int j=0;j<=n;++j)
			if(x.a[i][j])
				for(int k=0;k<=n;++k)
					tmp.a[i][k]+=x.a[i][j]*y.a[j][k];
	return tmp;
}

Matrix exp(Matrix x,int n)
{
	Matrix tmp;
	tmp.init();
	while(n){
		if(n&1) tmp=tmp*x;
		x=x*x;
		n>>=1;
	}
	return tmp;
}
int main()
{
	while(scanf("%d%d%d",&n,&m,&k)==3){
		if(!n&&!m&&!k) break;
		memset(A.a,0,sizeof(A.a));
		A.a[0][0]=1;
		T.init();
		while(k--){
			char op[8];
			int x,y;
			scanf("%s",op);
			if(op[0]=='g'){
				scanf("%d",&x);
				++T.a[0][x];
			}else if(op[0]=='e'){
				scanf("%d",&x);
				for(int i=0;i<=n;++i)
					T.a[i][x]=0;
			}else{
				scanf("%d%d",&x,&y);
				for(int i=0;i<=n;++i)
					swap(T.a[i][x],T.a[i][y]);
			}		
		}
		Matrix ans=A*exp(T,m);
		for(int i=1;i<=n;++i)
			printf("%lld ",ans.a[0][i]);
		printf("\n");
	}
	return 0;	
} 

poj 3735 Training little cats 矩阵的幂

原文：http://blog.csdn.net/sepnine/article/details/44536929