http://poj.org/problem?id=3735
大致题意：
有n只猫，开始时每只猫有花生0颗，现有一组操作，由下面三个中的k个操作组成：
1. g i 给i只猫一颗花生米
2. e i 让第i只猫吃掉它拥有的所有花生米
3. s i j 将猫i与猫j的拥有的花生米交换
现将上述一组操作循环m次后，问每只猫有多少颗花生？
再一次感受到了矩阵的强大。。。循环m次，且m这么大，很容易想到构造转换矩阵，但如何构造是个问题。尤其是第一种操作，第i只猫增加一个花生。具体构造方法是把矩阵扩大为(n+1)*(n+1)的，初始化为单位矩阵，g i: a.mat[0][i] += 1; e i ：第i列全置为0； s i j: 第i、j列元素互换
这样形成转换矩阵后，循环m次，用矩阵快速幂求得，最后取矩阵第0行的1~n就是答案。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#define LL long long
#define _LL __int64
#define eps 1e-8
#define PI acos(-1.0)
using namespace std;
const int maxn = 105;
int n,k,m;
struct matrix
{
_LL mat[maxn][maxn];
//初始化为单位矩阵
void init()
{
memset(mat,0,sizeof(mat));
for(int i = 0; i <= 102; i++) //不知道为什么，102换成maxn就会崩，求解。
mat[i][i] = 1;
}
}a,res;
//矩阵相乘
matrix matrixMul(matrix x, matrix y)
{
matrix tmp;
memset(tmp.mat,0,sizeof(tmp.mat));
for(int i = 0; i <= n; i++)
{
for(int k = 0; k <= n; k++)
{
if(x.mat[i][k] == 0) continue;
for(int j = 0; j <= n; j++)
{
tmp.mat[i][j] += x.mat[i][k] * y.mat[k][j];
}
}
}
return tmp;
}
//矩阵求幂
matrix Mul(matrix x, int k)
{
matrix tmp;
tmp.init();
while(k)
{
if(k & 1)
tmp = matrixMul(tmp,x);
x = matrixMul(x,x);
k >>= 1;
}
return tmp;
}
int main()
{
char ch[4];
while(~scanf("%d %d %d",&n,&m,&k))
{
if(n == 0 && k == 0 && m == 0) break;
a.init();
int num1,num2;
while(k--)
{
scanf("%s",ch);
if(ch[0] == 'g')
{
scanf("%d",&num1);
a.mat[0][num1] += 1;
}
else if(ch[0] == 'e')
{
scanf("%d",&num1);
for(int i = 0; i <= n; i++)
a.mat[i][num1] = 0;
}
else
{
scanf("%d %d",&num1,&num2);
for(int i = 0; i <= n; i++)
swap(a.mat[i][num1],a.mat[i][num2]);
}
}
if(m == 0)
{
for(int i = 0; i < n;i++)
{
if(i == 0)printf("0");
else printf(" 0");
}
printf("\n");
continue ;
}
res = Mul(a,m);
for(int i = 1; i < n; i++)
printf("%I64d ",res.mat[0][i]);
printf("%I64d\n",res.mat[0][n]);
}
return 0;
}
poj 3735 Training little cats（构造矩阵）,布布扣,bubuko.com
poj 3735 Training little cats（构造矩阵）
原文：http://blog.csdn.net/u013081425/article/details/30505209