首页 > 代码库 > 送给圣诞夜的礼品

送给圣诞夜的礼品

2024-07-18 15:23:28   225人阅读

描述

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

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



联系
我们