整体思路

这道题的核心是处理多次重复的操作序列，由于直接模拟 $m$ 次操作（$m$ 可能高达 $10^9$ ）会超时，所以采用矩阵快速幂的思想，把每次操作序列的效果转化为矩阵变换，然后通过快速幂计算 $m$ 次重复操作后的最终变换，从而高效得到每只小猫的花生数量。

矩阵建模

• 扩展矩阵维度：构建一个 $(n + 1) \times (n + 1)$ 的矩阵（$n$ 是小猫数量 ），额外的一行一列用于处理“新增花生”这类操作（可以把最后一列看作记录每只小猫最终花生数的累加项，最后一行辅助计算 ）。初始时矩阵为单位矩阵，代表“无操作”时的状态（每只小猫花生数不变，自身对应位置为 $1$，其余为 $0$ ）。
• 操作转化为矩阵变换：
  • $g i$（第 $i$ 只小猫得 $1$ 颗花生 ）：对应矩阵第 $i$ 行、第 $n + 1$ 列的位置加 $1$。因为每次执行 $g i$，相当于在最终花生数的计算中，给第 $i$ 只小猫的总数额外加 $1$，通过矩阵乘法可以累积这个操作的效果。
  • $e i$（第 $i$ 只小猫吃掉所有花生 ）：将矩阵第 $i$ 行的所有元素置为 $0$。这样，后续不管之前这只小猫有多少花生（对应矩阵乘法中的累积结果 ），经过这一行的变换后都会被清零，模拟“吃空”的效果。
  • $s i j$（交换第 $i$ 只和第 $j$ 只小猫的花生 ）：交换矩阵的第 $i$ 行和第 $j$ 行。因为矩阵的行对应着每只小猫花生数的计算逻辑，交换行就相当于交换了两只小猫花生数的“计算规则”，从而实现花生数量的交换。

矩阵乘法优化（稀疏矩阵加速）

矩阵乘法常规的三重循环是 $O(N^3)$ 复杂度，这里利用操作矩阵的稀疏性（很多元素是 $0$ ）进行优化：
在 $Multi$ 函数中，先遍历行 $i$ 和中间维度 $k$，只有当 $a[i][k]$ 不为 $0$ 时，才继续遍历列 $j$ 并进行乘法累加操作；同时对矩阵 $b$ 也做类似判断（$b[k][j]$ 不为 $0$ 时才计算 ）。这样能跳过大量乘以 $0$ 的无效运算，大幅减少计算量，让矩阵快速幂在合理时间内完成。

快速幂计算

• 把 $m$ 次操作序列的重复，转化为矩阵的 $m$ 次幂运算。利用快速幂的二进制分解思想，将 $m$ 拆成若干 $2$ 的幂次之和（如 $m = 5$ 拆成 $4 + 1$ ）。
• 初始化结果矩阵 $b$ 为单位矩阵（代表初始无操作的状态 ），然后遍历 $m$ 的二进制位，当当前位为 $1$ 时，将结果矩阵 $b$ 与当前操作矩阵 $a$ 相乘（累积操作效果 ）；之后将操作矩阵 $a$ 自乘（相当于翻倍操作次数 ），直到处理完 $m$ 的所有二进制位。

结果输出

最终结果矩阵 $b$ 的第 $i$ 行、第 $n + 1$ 列的元素，就对应第 $i$ 只小猫经过 $m$ 次操作序列后拥有的花生数量，按顺序输出这些元素即可。

标程

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

#define maxn 111  // 定义矩阵最大维度，n最大为100，加上额外一行一列，设为111足够

long long a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];  // a存操作矩阵，b存结果矩阵，c存临时中间矩阵
int i, j, e, n, m, k;  // 循环变量、题目输入的n/m/k等
char op[9];  // 存储操作类型（g/e/s）

// 矩阵乘法函数，实现a = a * b 的效果（这里的乘法是自定义的矩阵变换乘法，用于累积操作效果）
void Multi(long long a[maxn][maxn], long long b[maxn][maxn]) {
    memset(c, 0, sizeof(c));  // 每次乘法先清空临时矩阵c
    for (i = 1; i <= n + 1; ++i) {  // 遍历结果矩阵的行
        for (k = 1; k <= n + 1; ++k) {  // 遍历中间维度（类似矩阵乘法的k维度）
            if (a[i][k]) {  // 优化：a[i][k]为0时，相乘无意义，跳过
                for (j = 1; j <= n + 1; ++j) {  // 遍历结果矩阵的列
                    if (b[k][j]) {  // 优化：b[k][j]为0时，相乘无意义，跳过
                        c[i][j] += a[i][k] * b[k][j];  // 矩阵乘法累加
                    }
                }
            }
        }
    }
    // 将临时矩阵c的结果赋值回a，完成a = a * b 的更新
    for (i = 1; i <= n + 1; ++i) {
        for (j = 1; j <= n + 1; ++j) {
            a[i][j] = c[i][j];
        }
    }
}

int main() {
    // 多组测试用例，直到输入0 0 0为止
    while (scanf("%d%d%d", &n, &m, &k) && !(n == 0 && m == 0 && k == 0)) {
        memset(a, 0, sizeof(a));  // 初始化操作矩阵
        memset(b, 0, sizeof(b));  // 初始化结果矩阵
        // 初始化为单位矩阵，这样初始状态下，矩阵乘法不会改变结果（类似乘法中的1）
        for (i = 1; i <= n + 1; ++i) {
            a[i][i] = b[i][i] = 1;
        }

        // 读取并处理k个操作，构建操作矩阵a
        while (k--) {
            scanf("%s%d", op, &i);
            if (op[0] == 'g') {  // 处理g操作：第i只猫得1颗花生
                ++a[i][n + 1];
            }
            if (op[0] == 'e') {  // 处理e操作：第i只猫花生清零
                for (j = 0; j <= n + 1; ++j) {
                    a[i][j] = 0;
                }
            }
            if (op[0] == 's') {  // 处理s操作：交换i和j的花生（交换矩阵的i行和j行）
                scanf("%d", &j);
                for (e = 1; e <= n + 1; ++e) {
                    swap(a[i][e], a[j][e]);
                }
            }
        }

        // 快速幂计算：将操作矩阵a的m次幂作用到结果矩阵b上
        while (m) {
            if (m & 1) {  // 如果m的当前二进制位为1，将结果矩阵b与操作矩阵a相乘
                Multi(b, a);
            }
            Multi(a, a);  // 操作矩阵a自乘，相当于操作次数翻倍
            m >>= 1;  // m右移一位，处理下一个二进制位
        }

        // 输出每只小猫最终的花生数量（结果矩阵b的第i行第n+1列）
        for (i = 1; i <= n; ++i) {
            printf("%lld ", b[i][n + 1]);
        }
        printf("\n");
    }
    return 0;
}