矩阵乘法

题意：一个一维数组，全为0，对它进行一系列操作，包括某位＋1，某位清零，交换某两位。将这一系列操作进行m次。问数组的最终情况。

分析：数组的元素从第一位开始，把第0位附为1，我们构造一个n*n矩阵使得原1＊n矩阵每乘以一次这个矩阵,得到的结果就相当于进行了一次一系列操作。然后用矩阵快速幂即可。构造矩阵的方法是：操作一，0行某列位置元素++；操作二，某列清零；操作三，交换两列。

矩阵乘法需要优化：

    for (int i = 0; i < a.x; i++)

        for (int k = 0; k < a.y; k++)

            if (a.a[i][k])

                for (int j = 0; j < b.y; j++)

                    ret.a[i][j] += a.a[i][k] * b.a[k][j];

否则超时。

#include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; #define maxn 110 struct Matrix {
     long long x, y; long long a[maxn][maxn]; } f, temp; long long n, m, r; Matrix mul(Matrix &a, Matrix &b) {
         Matrix ret;     memset(ret.a, 0, sizeof(ret.a));     ret.x = a.x;     ret.y = b.y; for (int i = 0; i < a.x; i++) for (int k = 0; k < a.y; k++) if (a.a[i][k]) for (int j = 0; j < b.y; j++)                     ret.a[i][j] += a.a[i][k] * b.a[k][j]; return ret; } Matrix power(Matrix &a, long long n) {
         Matrix m = a;     Matrix ret;     memset(ret.a, 0, sizeof(ret.a)); for (int i = 0; i < a.x; i++)         ret.a[i][i] = 1;     ret.x = ret.y = a.x; while (n > 0)     {
     if (1 & n)             ret = mul(ret, m);         m = mul(m, m);         n >>= 1;     } return ret; } void input() {
         memset(f.a, 0, sizeof(f.a)); for (int i = 0; i <= n; i++)         f.a[i][i] = 1;     f.x = f.y = n + 1; for (int i = 0; i < m; i++)     {
     int a, b; char ch[2];         scanf("%s", ch); if (ch[0] == 'g')         {
                 scanf("%d", &a);             f.a[0][a]++;         } else if (ch[0] == 'e')         {
                 scanf("%d", &a); for (int j = 0; j <= n; j++)                 f.a[j][a] = 0;         } else         {
                 scanf("%d%d", &a, &b); for (int j = 0; j <= n; j++)                 swap(f.a[j][a], f.a[j][b]);         }     } } void work() {
         Matrix ans;     memset(ans.a, 0, sizeof(ans.a));     ans.x = 1;     ans.y = n + 1;     ans.a[0][0] = 1;     ans = mul(ans, f);     printf("%lld", ans.a[0][1]); for (int i = 2; i <= n; i++)         printf(" %lld", ans.a[0][i]);     putchar('\n'); } int main() {
     //freopen("t.txt", "r", stdin);     while (scanf("%lld%lld%lld", &n, &r, &m), n | r | m)     {
             input();         f = power(f, r);         work();     } return 0; }