矩阵快速幂 POJ 3735 Training little cats

题目传送门

/*
    题意：k次操作，g：i猫+1, e：i猫eat，s：swap
    矩阵快速幂：写个转置矩阵，将k次操作写在第0行，定义A = {1，0, 0, 0...}除了第一个外其他是猫的初始值
        自己讲太麻烦了，网上有人讲的很清楚，膜拜之
    详细解释：http://www.cppblog.com/y346491470/articles/157284.html
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 1e2 + 10;
const int INF = 0x3f3f3f3f;
struct Mat  {
    ll m[MAXN][MAXN];
    Mat ()  {
        memset (m, 0, sizeof (m));
    }
    void init(void) {
        for (int i=0; i<MAXN; ++i)  m[i][i] = 1;
    }
};
int n, m, k;

Mat operator * (Mat &a, Mat &b) {
    Mat ret;
    for (int k=0; k<=n; ++k)    {
        for (int i=0; i<=n; ++i)    {
            if (a.m[i][k])  {
                for (int j=0; j<=n; ++j)    {
                    ret.m[i][j] += a.m[i][k] * b.m[k][j];
                }
            }
        }
    }
    return ret;
}

Mat operator ^ (Mat x, int n)   {
    Mat ret;    ret.init ();
    while (n)   {
        if (n & 1)  ret = ret * x;
        x = x * x;
        n >>= 1;
    }
    return ret;
}

int main(void)  {       //POJ 3735 Training little cats
    while (scanf ("%d%d%d", &n, &m, &k) == 3)   {
        if (!n && !m && !k) break;
        Mat A, T;   A.m[0][0] = 1;  T.init ();
        char op[5]; int p, q;
        while (k--) {
            scanf ("%s", op);
            if (op[0] == 'g')    {
                scanf ("%d", &p);   T.m[0][p]++;
            }
            else if (op[0] == 'e')  {
                scanf ("%d", &p);
                for (int i=0; i<=n; ++i)    T.m[i][p] = 0;
            }
            else    {
                scanf ("%d%d", &p, &q);
                for (int i=0; i<=n; ++i)    swap (T.m[i][p], T.m[i][q]);
            }
        }
        Mat ans = A * (T ^ m);
        for (int i=1; i<=n; ++i)    printf ("%I64d%c", ans.m[0][i], (i==n) ? '
' : ' ');
    }

    return 0;
}