https://vijos.org/p/1049
P1049送给圣诞夜的礼品
Accepted
标签：
组合数学
送给圣诞夜的礼物
[显示标签]
返回代码界面 |
关闭
Pascal
PascalCC++Python 2.xJava
取消 |
清空代码
描述
当小精灵们把贺卡都书写好了之后。礼品准备部的小精灵们已经把所有的礼品都制作好了。可是由于精神消耗的缘故，他们所做的礼品的质量越来越小，也就是说越来越不让圣诞老人很满意。可是这又是没有办法的事情。
于是圣诞老人把礼品准备部的小精灵们聚集起来，说明了自己的看法：“现在你们有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题意：初始数列为1.2.3...n；然后给了m个操作，每个操作都有n个数，表示把第a[i]的数放到第i位置上了，题目让求经过k次操作后的数列分析：后的序列。
m<=10, k<2^31。
首先将这m个置换“合并”起来（算出这m个置换的乘积），然后接下来我们需要执行这个置换k/m次（取整，若有余数则剩下几步模拟即可）。注意任意一个置换都可以表示成矩阵的形式。例如，将1 2 3 4置换为3 1 2 4，相当于下面的矩阵乘法：（第i行第a[i] 为1；因为要把第a[i]个数放到第i个位置） 置换k/m次就相当于在前面乘以k/m个这样的矩阵。我们可以二分计算出该矩阵的k/m次方，再乘以初始序列即可。做出来了别忙着高兴，得意之时就是你灭亡之日，别忘了最后可能还有几个置换需要模拟。
1 #include <iostream>
2 #include <cstring>
3 #include <algorithm>
4 #include <cstdio>
5 using namespace std;
6 struct Mat
7 {
8 int mat[
110][
110];
9 };
10 Mat p[
15];
11 int n,m,k;
12 Mat
operator *
(Mat x, Mat y)
13 {
14 Mat c;
15 memset(c.mat,
0,
sizeof(c.mat));
16 for(
int t =
1; t <= n; t++
)
17 {
18 for(
int i =
1; i <= n; i++
)
19 {
20 for(
int j =
1; j <= n; j++
)
21 c.mat[i][j] += x.mat[i][t] *
y.mat[t][j];
22 }
23 }
24 return c;
25 }
26 Mat
operator ^ (Mat x,
int t)
27 {
28 Mat c;
29 for(
int i =
1; i <= n; i++
)
30 for(
int j =
1; j <= n; j++
)
31 c.mat[i][j] = (i ==
j);
32 while(t)
33 {
34 if(t &
1)
35 c = c *
x;
36 x = x *
x;
37 t >>=
1;
38 }
39 return c;
40 }
41 int main()
42 {
43 while(scanf(
"%d%d%d", &n,&m,&k) !=
EOF)
44 {
45 Mat res,c,a;
46 for(
int i =
1; i <= n; i++
)
47 a.mat[i][
1] =
i;
48
49 for(
int i =
1; i <= n; i++
)
50 for(
int j =
1; j <= n; j++
)
51 res.mat[i][j] = (i ==
j);
52
53 for(
int i =
1; i <= m; i++
)
54 {
55 memset(c.mat,
0,
sizeof(c.mat));
56 for(
int j =
1; j <= n; j++
)
57 {
58 scanf(
"%d", &p[i].mat[j][
1]);
59 c.mat[j][ p[i].mat[j][
1] ] =
1;
60 }
61 res = c *
res;
62 }
63
64 res = res ^ (k /
m);
65 a = res *
a;
66 int temp = k %
m;
67 for(
int i =
1; i <= temp; i++
)
68 {
69 memset(c.mat,
0,
sizeof(c.mat));
70 for(
int j =
1; j <= n; j++
)
71 c.mat[j][ p[i].mat[j][
1] ] =
1;
72 a = c *
a;
73 }
74 for(
int i =
1; i < n; i++
)
75 {
76 printf(
"%d ",a.mat[i][
1]);
77 }
78 printf(
"%d\n",a.mat[n][
1]);
79
80 }
81 return 0;
82 }
View Code
转载于:https://www.cnblogs.com/zhaopAC/p/5076303.html
相关资源：JAVA上百实例源码以及开源项目
