POJ3735 Training little cats DP,矩阵高速幂,稀疏矩阵优化

POJ3735 Training little cats DP,矩阵快速幂,稀疏矩阵优化

题目大意是，n只猫，有k个动作让它们去完成，并且重复m次，动作主要有三类gi,ei,s i j，分别代表第i只猫获得一个花生，第i只猫吃掉它自己所有的花生，第i只和第j只猫交换彼此的花生。k,n不超过100，m不超过1000,000,000，计算出最后每只猫还剩下多少个花生。

我们假设一个n维向量P，每个分量的值代表这n只猫所拥有的花生数，那么对于gi操作其实就是在第i维分量上加上1；对于ei，那就是在第i维分量上乘以0，说到这里，有木有感觉这很像3D坐标转化中的平移矩阵和缩放矩阵？没错，就是这个意思，现在知道g i 和 e i对应的操作，那么s i j 呢，第i维分量就是第i维分量乘以0加上第j维分量乘以1，第j维分量就是第i行分量乘以1加上第j行分量乘以0。

由于要支持平移操作，我们需要对向量再增加一维，并且一直保持1，转移矩阵也是 (n + 1) * (n + 1)，初始时该矩阵为单位矩阵，我们将每一个操作转化成矩阵，再让向量P与其相乘，由于满足结合律，我们可以先让这k个矩阵先相称，然后对结果作m次幂，因为m很大，用快速幂来优化就行，但是到这里直接提交代码的话会TLE，为什么呢。。。还是矩阵相乘复杂度过高了，我们发现这个矩阵大多数元素是0，所以在相乘的时候可以略去很多不需要的乘法，具体优化看代码吧。

#include <stdio.h>
#include <vector>
#include <math.h>
#include <string.h>
#include <string>
#include <iostream>
#include <queue>
#include <list>
#include <algorithm>
#include <stack>
#include <map>
#include <time.h>
using namespace std;

#define MAXSIZE 101
typedef long long MYTYPE;
MYTYPE States[MAXSIZE][MAXSIZE];

void VectorMulMatrix(MYTYPE v[MAXSIZE], MYTYPE a[][MAXSIZE], MYTYPE res[MAXSIZE])
{
	memset(res, 0, sizeof(MYTYPE)* MAXSIZE);
	for (int i = 0; i < MAXSIZE; i++)
	{
		for (int j = 0; j < MAXSIZE;j++)
		{
			res[i] += (v[j] * a[j][i]);
		}
	}
}

void Product(MYTYPE a[][MAXSIZE], MYTYPE b[][MAXSIZE], MYTYPE res[][MAXSIZE])
{
	memset(res, 0, sizeof(MYTYPE)* MAXSIZE * MAXSIZE);
	for (int i = 0; i < MAXSIZE; i++)
	{
		for (int j = 0; j < MAXSIZE; j++)
		{
			if (a[i][j])
			{
				for (int k = 0; k < MAXSIZE; k++)
				{
					res[i][k] += (a[i][j] * b[j][k]);
				}
			}
			
		}
	}
}

void QProduct(MYTYPE p[][MAXSIZE], MYTYPE res[][MAXSIZE], int n)
{
	memset(res, 0, sizeof(MYTYPE)* MAXSIZE * MAXSIZE);
	MYTYPE tmp[2][MAXSIZE][MAXSIZE];
	MYTYPE tmpres[MAXSIZE][MAXSIZE];
	memcpy(tmp[0], p, sizeof(MYTYPE)* MAXSIZE * MAXSIZE);
	int i = 0;
	for (int k = 0; k < MAXSIZE; k++)
	{
		res[k][k] = 1;
	}
	while (n)
	{
		if (n & 1)
		{
			memcpy(tmpres, res, sizeof(MYTYPE)* MAXSIZE * MAXSIZE);
			Product(tmpres, tmp[i & 1], res);
		}
		Product(tmp[i & 1], tmp[i & 1], tmp[(i + 1) & 1]);
		i++;
		n = n >> 1;
	}
}

void IdentityMatrix(MYTYPE a[][MAXSIZE])
{
	memset(a, 0, sizeof(MYTYPE)* MAXSIZE * MAXSIZE);
	for (int i = 0; i < MAXSIZE; i++)
	{
		a[i][i] = 1;
	}
}

int main()
{
#ifdef _DEBUG
	freopen("e:\\in.txt", "r", stdin);
#endif
	int n, m, k;
	MYTYPE CurState[MAXSIZE][MAXSIZE];
	MYTYPE tmpState[MAXSIZE][MAXSIZE];
	MYTYPE tmpRes[MAXSIZE];
	MYTYPE cur[MAXSIZE];
	while (scanf("%d %d %d\n", &n, &m, &k) != EOF)
	{
		if (n == 0 && m == 0 && k == 0)
		{
			break;
		}
		memset(cur, 0, sizeof(MYTYPE)* MAXSIZE);
		memset(tmpRes, 0, sizeof(MYTYPE)* MAXSIZE);
		cur[MAXSIZE - 1] = 1;
		char op;
		IdentityMatrix(States);
		for (int i = 0; i < k; i++)
		{
			IdentityMatrix(CurState);
			scanf("%c", &op);
			if (op == 'g')
			{
				int value;
				scanf("%d\n", &value);
				CurState[MAXSIZE - 1][value - 1] = 1;
			}
			else if (op == 'e')
			{
				int value;
				scanf("%d\n", &value);
				CurState[value - 1][value - 1] = 0;
				CurState[MAXSIZE - 1][value - 1] = 0;
			}
			else
			{
				int value1, value2;
				scanf("%d %d\n", &value1, &value2);
				CurState[value1 - 1][value1 - 1] = 0;
				CurState[value2 - 1][value2 - 1] = 0;
				CurState[value2 - 1][value1 - 1] = 1;
				CurState[value1 - 1][value2 - 1] = 1;
			}
			Product(States, CurState, tmpState);
			memcpy(States, tmpState, sizeof(MYTYPE)* MAXSIZE * MAXSIZE);
		}
		if (m != 0)
		{
			QProduct(States, tmpState, m);
			VectorMulMatrix(cur, tmpState, tmpRes);
		}
		
		for (int i = 0; i < n; i++)
		{
			printf("%I64d ", tmpRes[i]);
		}
		printf("\n");
	}
	return 0;
}

POJ3735 Training little cats DP,矩阵高速幂,稀疏矩阵优化

相关推荐