//zory 【Vijos1049】送给圣诞夜的礼品 | Zory的个人博客

【Vijos1049】送给圣诞夜的礼品

来源和评测点

Vivian Snow
Vijos1049
Caioj1482

题目

【题目大意】
有n个数,也就是说初始序列为1,2,3…n
m种置换方式(有m行),每行有n个数字,这些数字互不相同而且每个数字都在1到n之间。
置换操作方式为设这一行操作的第i个数字为a[i],那么就把原来序列中的第a[i]个数放到新的序列的第i的位置上,
然后组成一个新的序列。从第一种置换方式开始操作,一直到最后一种操作,重复上面的操作方式。
当最后一种操作结束后,组成了的序列又按照第一种来操作,一直循环下去,直到一共操作了k次为止
【输入格式】
第一行三个数,n(1<=n<=100),m(1<=m<=10)和k(1<=k<=2^31-1)
接下来m行,每行有n个数
【输出格式】
一行,一共有n个数,表示最终序列。n个数之间用一个空格隔开,行尾没有空格,需要回车。
【输入样例】
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
【输出样例】
2 4 6 3 5 1 7

分析

真心简单
把m个操作的每个操作变成一个操作矩阵
这m个矩阵相乘,然后快速幂k次,与原始矩阵相乘即可

哦对了,记得因为不满足交换律,结合顺序必须依照原本的顺序
如果是列向量的话,就是越左越晚

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
//*******************全局常量*******************
const int MAXN=110;
//*******************全局定义*******************
struct matrix
{
int row,col;
int p[MAXN][MAXN];
matrix()
{
memset(p,0,sizeof(p));
}
};
//*******************全局变量*******************
matrix c[20];
//*******************实现*******************
matrix cheng(matrix a,matrix b)
{
matrix c;
int n=a.row,m=a.col,p=b.col;
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++)
for(int k=1;k<=m;k++)
c.p[i][j]+=a.p[i][k]*b.p[k][j];
c.row=n;c.col=p;
return c;
}
matrix jia(matrix a,matrix b)
{
matrix c;c.row=a.row;c.col=a.col;
for(int i=1;i<=c.row;i++)
for(int j=1;j<=c.col;j++)
c.p[i][j]=a.p[i][j]+b.p[i][j];
return c;
}
matrix pre(int fn)
{
matrix c;
for(int i=1;i<=fn;i++) c.p[i][i]=1;
c.row=c.col=fn;
return c;
}
matrix power(matrix a,int e)
{
matrix c=pre(a.row);
while(e>0)
{
if(e%2==1) --e,c=cheng(c,a);//a*c也行
a=cheng(a,a);e/=2;
}
return c;
}
//*******************主函数*******************
int main()
{
int n,m,k;scanf("%d%d%d",&n,&m,&k);
matrix s;s.row=n;s.col=1;for(int i=1;i<=n;i++) s.p[i][1]=i;
matrix f=pre(n);
for(int i=1;i<=m;i++)
{
c[i].row=c[i].col=n;
for(int j=1;j<=n;j++)
{
int t;
scanf("%d",&t);
c[i].p[j][t]=1;
}
f=cheng(c[i],f);
}
int a=k/m,b=k%m;
matrix ans=power(f,a);
for(int i=1;i<=b;i++) ans=cheng(c[i],ans);//补上多余
ans=cheng(ans,s);//注意顺序
for(int i=1;i<=n;i++) printf("%d ",ans.p[i][1]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-01/送给圣诞夜的礼品.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!