本文主要是介绍poj 3735 Training little cats（构造矩阵），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=3735
大致题意：
有n只猫，开始时每只猫有花生0颗，现有一组操作，由下面三个中的k个操作组成：
1. g i 给i只猫一颗花生米
2. e i 让第i只猫吃掉它拥有的所有花生米
3. s i j 将猫i与猫j的拥有的花生米交换
现将上述一组操作循环m次后，问每只猫有多少颗花生？
很明显，要先构造矩阵，构造一个(n+1)*(n+1)的矩阵a,初始化为单位矩阵。
g i : a[i][n+1] += 1;
e i : a[i][j] = 0;（1 <= j <= n+1）
s i j : swap(a[i][k],a[j][k])(1 <= k <= n+1)
然后矩阵快速幂就ok了。
注意m很大，k也不小，要用long long .
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
#define C 240
#define S 20
using namespace std;
const int maxn = 110;
int n,m,k;struct matrix
{LL mat[maxn][maxn];void init(){memset(mat,0,sizeof(mat));for(int i = 1; i <= n+1; i++)mat[i][i] = 1;}
}a,b;matrix mul(matrix a, matrix b)
{matrix ans;memset(ans.mat,0,sizeof(ans.mat));for(int i = 1; i <= n+1; i++){for(int k = 1; k <= n+1; k++){if(a.mat[i][k] == 0) continue;for(int j = 1; j <= n+1; j++)ans.mat[i][j] += a.mat[i][k] * b.mat[k][j];}}return ans;
}matrix pow(matrix a, int nn)
{matrix ans;ans.init();while(nn){if(nn&1)ans = mul(ans,a);a = mul(a,a);nn >>= 1;}return ans;
}int main()
{char ch[3];int x,y;while(~scanf("%d %d %d",&n,&m,&k)){if(n == 0 && m == 0 && k == 0) break;a.init();memset(b.mat,0,sizeof(b.mat));b.mat[n+1][1] = 1;while(k--){scanf("%s",ch);if(ch[0] == 'g'){scanf("%d",&x);a.mat[x][n+1] += 1;}else if(ch[0] == 'e'){scanf("%d",&x);for(int i = 1; i <= n+1; i++)a.mat[x][i] = 0;}else{scanf("%d %d",&x,&y);for(int i = 1; i <= n+1; i++)swap(a.mat[x][i],a.mat[y][i]);}}a = pow(a,m);matrix ans = mul(a,b);for(int i = 1; i <= n; i++){printf("%lld",ans.mat[i][1]);if(i == n) printf("\n");else printf(" ");}}return 0;}
这篇关于poj 3735 Training little cats（构造矩阵）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
