程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3735 Training little cats（構造矩陣）

poj 3735 Training little cats（構造矩陣）

編輯：C++入門知識

大致題意：

有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 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#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(
);
            continue ;
		}
        res = Mul(a,m);
        for(int i = 1; i < n; i++)
			printf(%I64d ,res.mat[0][i]);
		printf(%I64d
,res.mat[0][n]);
	}

	return 0;
}