/*
题意：有n只猫咪，开始时每只猫咪有花生0颗，现有一组操作，由下面三个中的k个操作组成：
1. g i：给i只猫咪一颗花生米；
2. e i：让第i只猫咪吃掉它拥有的所有花生米；
3. s i：j 将猫咪i与猫咪j的拥有的花生米交换。
现将上述一组操作做m次后，问每只猫咪有多少颗花生？

思路：m达到10^9，显然不能直接算。
因为k个操作给出之后就是固定的，所以想到用矩阵，矩阵快速幂可以把时间复杂度降到O(log m)。问题转化为如何构造转置矩阵？
有一个很好的办法就是添加一个辅助，使初始矩阵变为一个n+1元组，编号为0到n，下面以3个猫为例：
定义初始矩阵A = [x y z 1]，最后一个元素固定为1，0~n-1分别为对应的每一只猫所拥有的花生数。
再定义一个n+1维的方阵Mat，初始化为单位矩阵，即Mat最初为：
|1 0 0 0|
|0 1 0 0|
|0 0 1 0|
|0 0 0 1|
，最后一行的前n个元素表示3只猫所拥有的花生数x、y、z，最开始的时候，3只猫都没有花生米，则Mat转化为：
|1 0 0 0|
|0 1 0 0|
|0 0 1 0|
|0 0 0 1|
，对于第一种操作g i，给i只猫咪一颗花生米,在单位矩阵基础上使Mat[n][i]变为1，例如g 1，表示给第0只猫咪一颗花生米：
|1 0 0 0|
|0 1 0 0|
|0 0 1 0|
|1 0 0 1|
，显然
                    |1 0 0 0|
A*Mat = [x y z 1] * |0 1 0 0| = [x+1 y z 1]
                    |0 0 1 0|
                    |1 0 0 1|
；对于第二种操作e i，让第i只猫咪吃掉它拥有的所有花生米，在单位矩阵基础上使Mat[i][i] = 0, 例如e 2，让第1只猫咪吃掉它拥有的所有花生米，需要使Mat[1][1]为0：
|1 0 0 0|
|0 0 0 0|
|0 0 1 0|
|0 0 0 1|
，显然
                    |1 0 0 0|
A*Mat = [x y z 1] * |0 0 0 0| = [x 0 z 1]
                    |0 0 1 0|
                    |0 0 0 1|
；对于第三种操作s i j，将猫咪i与猫咪j的拥有的花生米交换，在单位矩阵基础上使第i列与第j互换，例如s 2 3，让第1只猫咪和第2只猫咪的花生互换，需要在Mat矩阵中将第1列和第2列互换：
|1 0 0 0|
|0 0 1 0|
|0 1 0 0|
|0 0 0 1|
，显然
                    |1 0 0 0|
A*Mat = [x y z 1] * |0 0 1 0| = [x z y 1]
                    |0 1 0 0|
                    |0 0 0 1|
。现在，对于每一个操作都可以得到一个操作矩阵，把k个操作矩阵相乘可以得到一个新的矩阵T。
A * T 表示我们经过一组操作，类似我们可以得到经过m组操作的矩阵为 A * (T ^ m), 最终矩阵的[n][0~n-1]即为答案。
上述的做法比较直观，但是实现过于麻烦，因为要构造k个不同矩阵。
观察以下矩阵相乘的结果：
            |1 0 0 0|
[p q r 1] * |0 1 0 0| = [p+x  q+y  z+r  1]
            |0 0 1 0|
            |x y z 1|
相乘的结果是把p平移了x，q平移了y，r平移了z。
假设x、y、z分别表示某个操作前，3只猫咪已有的花生数，将A矩阵改为[0 0 0 1] ，
再将Mat矩阵改为
|1 0 0 0|
|0 1 0 0|
|0 0 1 0|
|x y z 1|
则：
                    |1 0 0 0|
A*Mat = [0 0 0 1] * |0 1 0 0| = [x y z 1]
                    |0 0 1 0|
                    |x y z 1|
相当于是获取了Mat矩阵的最后一行。再观察下面的矩阵相乘：
此时，
对于第一种操作g i，给i只猫咪一颗花生米，例如g 1，表示给第0只猫咪一颗花生米，可以用下面的矩阵相乘表示：
|1 0 0 0|   |1 0 0 0|   | 1  0  0  0|   
|0 1 0 0| * |0 1 0 0| = | 0  1  0  0|
|0 0 1 0|   |0 0 1 0|   | 0  0  1  0|
|x y z 1|   |1 0 0 1|   |x+1 y  z  1|
相当于给相乘前第一个矩阵的最后一行的第i-1列的元素加1，结果矩阵的最后一行的前n个元素表示执行g 1操作后n只猫咪各自拥有的花生数。
对于第二种操作e i，让第i只猫咪吃掉它拥有的所有花生米，例如e 2，让第1只猫咪吃掉它拥有的所有花生米，可以用下面的矩阵相乘表示：
|1 0 0 0|   |1 0 0 0|   | 1  0  0  0|
|0 1 0 0| * |0 0 0 0| = | 0  0  0  0|
|0 0 1 0|   |0 0 1 0|   | 0  0  1  0|
|x y z 1|   |0 0 0 1|   | x  0  z  1|
相当于给相乘前第一个矩阵的第i-1列的所有元素清0，结果矩阵的最后一行的前n个元素表示执行e 2操作后n只猫咪各自拥有的花生数。
对于第三种操作s i j，将猫咪i与猫咪j的拥有的花生米交换，例如s 2 3，让第1只猫咪和第2只猫咪的花生互换，可以用下面的矩阵相乘表示：
|1 0 0 0|   |1 0 0 0|   | 1  0  0  0|
|0 1 0 0| * |0 0 1 0| = | 0  0  1  0|
|0 0 1 0|   |0 1 0 0|   | 0  1  0  0|
|x y z 1|   |0 0 0 1|   | x  z  y  1|
相当于给相乘前第一个矩阵的第i-1列和第j-1列互换，结果矩阵的最后一行的前n个元素表示执行s 2 3操作后n只猫咪各自拥有的花生数。
这样实现的话，我们始终在处理一个矩阵，免去构造k个矩阵的麻烦。

样例说明:初始状态|0 0 0 1|，

|1 0 0 0|       |1 0 0 0|       |1 0 0 0|       |1 0 0 0|         |0 1 0 0|       |0 1 0 0|       |0 0 0 0|
|0 1 0 0|       |0 1 0 0|       |0 1 0 0|       |0 1 0 0|         |1 0 0 0|       |1 0 0 0|       |1 0 0 0|
|0 0 1 0|->(g 1)|0 0 1 0|->(g 2)|0 0 1 0|->(g 2)|0 0 1 0|->(s 1 2)|0 0 1 0|->(g 3)|0 0 1 0|->(e 2)|0 0 1 0|
|0 0 0 1|       |1 0 0 1|       |1 1 0 1|       |1 2 0 1|         |2 1 0 1|       |2 1 1 1|       |2 0 1 1|
最后3只猫咪各自拥有的花生数是2、0、1。
*/

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdio>
using namespace std;

class Matrix
{
protected:
	//long long ** arr;
	long long arr[105][105];
	int m;
	int n;
public:
	Matrix(int m, int n, int** a = NULL);
	Matrix(const Matrix& rhs);
	virtual ~Matrix();
	long long * operator[](int i);
	Matrix& operator = (const Matrix& rhs);
	Matrix operator * (const Matrix& rhs) const;
};

Matrix::Matrix(int m, int n, int** a) : m(m), n(n)
{
	//arr = new long long *[m];
	//for (int i = 0; i < m; i++)
	//{
	//	arr[i] = new long long [n];
	//	if (a && a[i])
	//	{
	//		for (int j = 0; j < n; j++)
	//		{
	//			arr[i][j] = a[i][j];
	//		}
	//	}
	//}
}

Matrix::Matrix(const Matrix& rhs) : m(rhs.m), n(rhs.n)
{
	//arr = new long long*[m];
	//for (int i = 0; i < m; i++)
	//{
	//	arr[i] = new long long[n];
	//}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			arr[i][j] = rhs.arr[i][j];
		}
	}
}

Matrix::~Matrix()
{
	//for (int i = 0; i < m; i++)
	//{
	//	delete[] arr[i];
	//}
	//delete[] arr;
}

long long* Matrix::operator[](int i)
{
	return arr[i];
}

Matrix& Matrix::operator = (const Matrix& rhs)
{
	//for (int i = 0; i < m; i++)
	//{
	//	delete[] arr[i];
	//}
	//delete[] arr;
	m = rhs.m;
	n = rhs.n;
	//arr = new long long *[m];
	//for (int i = 0; i < m; i++)
	//{
	//	arr[i] = new long long [n];
	//}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			arr[i][j] = rhs.arr[i][j];
		}
	}
	return *this;
}

Matrix Matrix::operator * (const Matrix& rhs) const
{
	Matrix result(this->m, rhs.n);
	for (int i = 0; i < this->m; i++)
	{
		for (int j = 0; j < rhs.n; j++)
		{
			result.arr[i][j] = 0;
		}
	}
	for (int i = 0; i < this->m; i++)
	{
		for (int j = 0; j < this->n; j++)
		{
			if (arr[i][j] != 0) // 必须这么写，否则超时，因为是稀疏矩阵
			{
				for (int k = 0; k < rhs.n; k++)
				{
					result.arr[i][k] += arr[i][j] * rhs.arr[j][k];
				}
			}
		}
	}
	return result;
}

class SMatrix : public Matrix
{
public:
	SMatrix(int n, int** a = NULL);
	SMatrix Exp(int k);
	void MakeE();
	SMatrix operator * (const SMatrix& rhs) const;
};

SMatrix::SMatrix(int n, int** a) : Matrix(n, n, a)
{
}

void SMatrix::MakeE()
{
	for (int i = 0; i < this->n; i++)
	{
		for (int j = 0; j < this->n; j++)
		{
			if (i == j)
			{
				arr[i][i] = 1;
			}
			else
			{
				arr[i][j] = 0;
			}
		}
	}
}

SMatrix SMatrix::operator * (const SMatrix& rhs) const
{
	SMatrix result(this->n);
	for (int i = 0; i < this->n; i++)
	{
		for (int j = 0; j < rhs.n; j++)
		{
			result.arr[i][j] = 0;
		}
	}
	for (int i = 0; i < this->n; i++)
	{
		for (int j = 0; j < this->n; j++)
		{
			if (arr[i][j]) // 必须这么写，否则超时
			{
				for (int k = 0; k < rhs.n; k++)
				{
					result.arr[i][k] += arr[i][j] * rhs.arr[j][k];
				}
			}
		}
	}
	return result;
}

SMatrix SMatrix::Exp(int k)
{
	if (k == 1)
	{
		return *this;
	}
	SMatrix result(this->n);
	// 先构造一个单位矩阵
	result.MakeE();
	if (k == 0)
	{
		return result;
	}
	SMatrix p(*this);
	while (k > 0)
	{
		if (k & 1) // 如果k为奇数
		{
			result = (p * result);
			//cout << "result\n";
			//result.Print();
		}
		p = p * p;
		k >>= 1;
	}
	return result;
}

class TrainingCat
{
protected:
	SMatrix* matrix;
	//SMatrix matrix;
	int n; // 猫咪数
	int m; // 重复次数
	int k; // 每一次有k个操作
	void Once();
public:
	void Solve();
};

void TrainingCat::Once()
{
	matrix->MakeE();
	//matrix.MakeE();
	while (k-- > 0)
	{
		char oper[5];
		scanf("%s", oper);
		if (oper[0] == 'g')
		{
			int x = 0;
			scanf("%d", &x);
			x--;
			(*matrix)[n][x]++;
			//matrix[n][x]++;
		}
		else if (oper[0] == 's')
		{
			int x = 0, y = 0;
			scanf("%d %d", &x, &y);
			x--;
			y--;
			if (x != y)
			{
				for (int i = 0; i < n + 1; i++)
				{
					swap((*matrix)[i][x], (*matrix)[i][y]);
					//swap(matrix[i][x], matrix[i][y]);
				}
			}
		}
		else
		{
			int x = 0;
			scanf("%d", &x);
			x--;
			for (int i = 0; i < n + 1; i++)
			{
				(*matrix)[i][x] = 0;
				//matrix[i][x] = 0;
			}
		}
	}
}

void TrainingCat::Solve()
{
	while (~scanf("%d %d %d", &n, &m, &k))
	{
		if (n == 0 && m == 0 && k == 0)
		{
			break;
		}
		matrix = new SMatrix(n + 1);
		//SMatrix matrix(n + 1);
		Once();

		SMatrix ans = matrix->Exp(m);
		//SMatrix ans = matrix.Exp(m);
		for (int i = 0; i < n; i++)
		{
			printf("%I64d ", ans[n][i]);
		}
		printf("\n");
		delete[] matrix;
	}
}

int main()
{
	TrainingCat obj;
	obj.Solve();
	return 0;
}

• %%%%% (4) ZHXS 2021-08-15 18:56:10