描述

当小精灵们把贺卡都书写好了之后。礼品准备部的小精灵们已经把所有的礼品都制作好了。可是由于精神消耗的缘故，他们所做的礼品的质量越来越小，也就是说越来越不让圣诞老人很满意。可是这又是没有办法的事情。

于是圣诞老人把礼品准备部的小精灵们聚集起来，说明了自己的看法：“现在你们有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

Copy

样例输出1

2 4 6 3 5 1 7

Copy

限制

各个测试点1s

提示

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

对于50%的数据，保证k<=500。这些数据每个数据点8分，其他的数据每个数据点12分。

题意概括：

依次给出对序列的 M 个置换操作，按顺序做 K 次置换，输出最后的序列（初始序列为从 1 到 N 的升序）；

解题思路：

转换为矩阵的初等行变换，注意左乘！注意左乘！注意左乘！

AC code：

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 #define LL long long

 using namespace std;

 const int MAXN = ;

 const int MAXM = ;

 int N, M;

 struct mat

 {

     int m[MAXN][MAXN];

 }base[MAXM];

 mat muti(mat a, mat b)

 {

     mat res;

     memset(res.m, , sizeof(res.m));

 //    for(int i = 1; i <= N; i++) res.m[i][i] = 1;

     for(int i = ; i <= N; i++)

     for(int j = ; j <= N; j++){

         if(a.m[i][j]){

             for(int k = ; k <= N; k++)

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

         }

     }

     return res;

 }

 mat qpow(mat a, int n)

 {

     mat res;

     memset(res.m, , sizeof(res.m));

     for(int i = ; i <= N; i++)

         res.m[i][i] = ;

     while(n){

         if(n&) res = muti(res, a);

         n>>=;

         a = muti(a, a);

     }

     return res;

 }

 int main()

 {

     int K, x;

     mat tmp;

     scanf("%d%d%d", &N, &M, &K);

     memset(tmp.m, , sizeof(tmp));

     for(int i = ; i <= N; i++) tmp.m[i][i] = ;

     for(int i = ; i <= M; i++){

         memset(base[i].m, , sizeof(base[i].m));

         for(int k = ; k <= N; k++){

             scanf("%d", &x);

             base[i].m[k][x] = ;

         }

         //see see

 //        for(int ii = 1; ii <= N; ii++){

 //            for(int jj = 1; jj <= N; jj++){

 //                printf("%d ", base[i].m[ii][jj]);

 //            }

 //            puts("");

 //        }

         tmp = muti(base[i], tmp);

     }

     int tt = K/M;

     tmp = qpow(tmp, tt);

     mat ans;

     memset(ans.m, , sizeof(ans.m));

     for(int i = ; i <= N; i++){

         ans.m[i][] = i;

     }

     ans = muti(tmp, ans);

     //see see

 //        for(int ii = 1; ii <= N; ii++){

 //            for(int jj = 1; jj <= N; jj++){

 //                printf("%d ", ans.m[ii][jj]);

 //            }

 //            puts("");

 //        }

     tt = K%M;

     for(int k = ; k <= tt; k++){

         ans = muti(base[k], ans);

     }

 //    mat ans;

 //    memset(ans.m, 0, sizeof(ans.m));

 //    for(int i = 1; i <= N; i++){

 //        ans.m[i][1] = i;

 //    }

 //    ans = muti(tmp, ans);

     for(int i = ; i < N; i++){

         printf("%d ", ans.m[i][]);

     }

     printf("%d\n", ans.m[N][]);

     return ;

 }

巴特西

VOJ1049 送给圣诞夜的礼品【矩阵经典4】

描述

格式

输入格式

输出格式

样例1

样例输入1

样例输出1

限制

提示

题意概括：

解题思路：

最新文章

热门文章

巴特西

VOJ1049 送给圣诞夜的礼品 【矩阵经典4】

描述

格式

输入格式

输出格式

样例1

样例输入1

样例输出1

限制

提示

题意概括：

解题思路：

最新文章

热门文章

VOJ1049 送给圣诞夜的礼品【矩阵经典4】