送給聖誕夜的禮品

描述

當小精靈們把賀卡都書寫好了之後。禮品準備部的小精靈們已經把所有的禮品都制作好了。可是由于精神消耗的緣故，他們所做的禮品的品質越來越小，也就是說越來越不讓聖誕老人很滿意。可是這又是沒有辦法的事情。

于是聖誕老人把禮品準備部的小精靈們聚集起來，說明了自己的看法：“現在你們有n個禮品，其品質也就是降序排列的。那麼為了使得這個禮品序列保持平均，不像現在這樣很有規律的降序，我這裡有一個清單。”

“清單共有m行，這m行都稱作操作（不是序列），每一行有n個數字，這些數字互不相同而且每個數字都在1到n之間。一開始，禮品的序列就是現在禮品所處的位置，也就是說，一開始禮品的序列就是1、2、3、4……n；那麼然後，我們看清單的第一行操作，設這一行操作的第i個數字為a[i]，那麼就把原來序列中的第a[i]個禮物放到現在這個序列的第i的位置上，然後組成新的禮物序列。然後，看清單的第二行操作……、第三行操作……一直到最後一行操作，重複上面的操作。當最後一行的操作結束，組成了的序列又按照第一行來操作，然後第二行操作……第三行操作……一直循環下去，直到一共操作了k行為止。最後生成的這個序列就是我們最終禮品送給孩子們的序列了。大家明白了嗎？”

“明白了！”

等聖誕老人一個微笑走後，大家卻開始忙碌了。因為m值可能很大很大，而小精靈們的操作速度有限。是以可能在聖誕老人去送禮物之前完成不了這個任務。讓他們很是惱火……

格式

輸入格式

第一行三個數，n，m和k。

接下來m行，每行n個數。

輸出格式

一行，一共n個數，表示最終的禮品序列。n個數之間用一個空格隔開，行尾沒有空格，需要回車。

樣例1

樣例輸入1[複制]

7 5 8

6 1 3 7 5 2 4

3 2 4 5 6 7 1

7 1 3 4 5 2 6

5 6 7 3 1 2 4

2 7 3 4 6 1 5

樣例輸出1[複制]

2 4 6 3 5 1 7

限制

各個測試點1s

提示

1<=n<=100；1<=m<=10；1<=k<=2^31-1。

對于50%的資料，保證k<=500。這些資料每個資料點8分，其他的資料每個資料點12分。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MX 110
using namespace std;
struct Node {
    int s[MX][MX];
};
int n, m, k;
long squ[MX], tsqu[MX];
Node data[MX];
Node Dir(Node a, Node b)
{
    Node c;
    memset(c.s, 0, sizeof(c.s));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                c.s[i][j] = (c.s[i][j] + (a.s[i][k] * b.s[k][j]));
    return c;
}
Node power(Node A, int d)
{
    Node B;
    memset(B.s, 0, sizeof(B.s));
    for (int i = 0; i < n; i++)
        B.s[i][i] = 1;
    while (d) {
        if (d & 1)
            B = Dir(A, B);
        A = Dir(A, A);
        d >>= 1;
    }
    return B;
}
int main()
{
    Node ans, A, AA;
    long an;
    while (~scanf("%d%d%d", &n, &m, &k))
    {
        memset(A.s, 0, sizeof(A.s));
        for (int i = 0; i < n; i++)
        {
            A.s[i][i] = 1; squ[i] = i + 1;
        }
        for (int i = 0; i < m; i++) {
            memset(AA.s, 0, sizeof(AA.s));
            for (int j = 0; j < n; j++) {
                scanf("%ld", &an);
                AA.s[j][an - 1] = 1;
            }
            data[i] = AA;//data儲存的是n*m的資料，
            A = Dir(AA, A);
        }
        int mod, div;
        mod = k % m;
        div = k / m;
        ans = power(A, div);
      /*  for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
              cout<<ans.s[i][j]<<" ";
              cout<<endl;
        }*/
        for (int i = 0; i < n; i++) {//在矩陣裡面是0和1，在這裡根據1的位置轉換成數字
            long tmp = 0;
            for (int j = 0; j < n; j++)
                tmp += ans.s[i][j] * squ[j];
            tsqu[i] = tmp;
        }
       // memcpy(squ, tsqu, sizeof(tsqu));
       //for(int i=0;i<n;i++)
       // cout<<squ[i]<<" ";
       // cout<<endl;
        for (int mm = 0; mm < mod; mm++) {//這裡就是剩餘的 (k%m)，整數倍後面的單獨用循環處理
            memcpy(squ, tsqu, sizeof(tsqu));//把tsqu數組裡面的内容複制給squ,也就是更新
            for (int i = 0; i < n; i++) {
                long tmp = 0;
                for (int j = 0; j < n; j++)
                    tmp += data[mm].s[i][j] * squ[j];//通過data[mm]裡面儲存的資料進行交換（1*squ[j]）
                tsqu[i] = tmp;                       //更新
            }
        }
        for (int i = 0; i < n; i++)
            printf("%ld%s", tsqu[i], i != n - 1 ? " " : "\n");
    }
    return 0;
}