【vijos1049】送给圣诞夜的礼品

题面

描述

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

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

题解

把每次操作看做一次置换，如：样例6 1 3 7 5 2 4

可看做矩阵

\[\begin{pmatrix}
0&0&0&0&0&1&0\\
1&0&0&0&0&0&0\\
0&0&1&0&0&0&0\\
0&0&0&0&0&0&1\\
0&0&0&0&1&0&0\\
0&1&0&0&0&0&0\\
0&0&0&1&0&0&0\\
\end{pmatrix}
\]

现在，做一个乘法

\[\begin{pmatrix}
1\\2\\3\\4\\5\\6\\7
\end{pmatrix}
\begin{pmatrix}
0&0&0&0&0&1&0\\
1&0&0&0&0&0&0\\
0&0&1&0&0&0&0\\
0&0&0&0&0&0&1\\
0&0&0&0&1&0&0\\
0&1&0&0&0&0&0\\
0&0&0&1&0&0&0\\
\end{pmatrix}=
\begin{pmatrix}
6\\1\\3\\7\\5\\2\\4
\end{pmatrix}
\]

矩阵马上变成了想要的样子。

所以先把所有置换都和起来再一次性置换

乘起所有矩阵，做一个快速幂

然后乘上多余没有乘的即可

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define rep(a,b,c) for(rg int a=b;a<=c;a++)

#define drep(a,b,c) for(rg int a=b;a>=c;a--)

#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

#define il inline

#define rg register

#define vd void

typedef long long ll;

il int gi(){

    rg int x=0;rg char ch=getchar();

    while(ch<'0'||ch>'9')ch=getchar();

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x;

}

int n,m,k;

struct Mat{

    int s[102][102];

    Mat(){memset(s,0,sizeof s);}

}I;

Mat operator +(Mat a,Mat b){

    Mat c;

    rep(i,1,n)rep(j,1,n){

		c.s[i][j]=a.s[i][j]+b.s[i][j];

		if(c.s[i][j]>n)c.s[i][j]-=n;

	}

    return c;

}

Mat operator *(Mat a,Mat b){

    Mat c;

    rep(i,1,n)rep(j,1,n)rep(l,1,n){

		c.s[i][j]+=a.s[i][l]*b.s[l][j];

		while(c.s[i][j]>n)c.s[i][j]-=n;

	}

    return c;

}

vd operator *=(Mat&a,Mat b){a=a*b;}

vd operator +=(Mat&a,Mat b){a=a+b;}

il Mat quick(Mat A,int b){

    if(b==1)return A;

    Mat s=quick(A,b>>1);

    if(b&1)return s*s*A;

    else return s*s;

}

Mat c[12];

int main(){

	n=gi(),m=gi(),k=gi();

	rep(i,1,n)I.s[i][i]=1;

	rep(i,1,m)rep(j,1,n)c[i].s[gi()][j]=1;

	Mat ji=I;

	rep(i,1,m)ji*=c[i];

	ji=quick(ji,k/m);

	rep(i,1,k%m)ji*=c[i];

	Mat k;

	rep(i,1,n)k.s[1][i]=i;

	k*=ji;

	rep(i,1,n)printf("%d ",k.s[1][i]);

    return 0;

}

巴特西

【vijos1049】送给圣诞夜的礼品

题面

描述

格式

输入格式

输出格式

样例1

样例输入1

样例输出1

限制

提示

题解

最新文章

热门文章