#P2227. [HNOI2001] 洗牌机

    ID: 1243 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp2001各省省选湖南图的建立建图最大流

[HNOI2001] 洗牌机

题目描述

剀剀和凡凡有 nn 张牌(依次标号为 1,2,,n1,2,\ldots,n)和一台洗牌机。假设 nn 是奇数。洗牌机的功能是进行如下的操作:对所有位置 i(1in)i(1\le i\le n),如果位置 ii 上的牌是 jj,而且位置 jj 上的牌是 kk,那么通过洗牌机后位置 ii 上的牌将是 kk

剀剀首先写下数值 1,2,,n1,2,\ldots,n 的一个随机排列:a1,a2,,ana_1,a_2,\ldots,a_n。然后他这样来排列牌的顺序:位置 aia_i 放置牌 ai+1a_{i+1}, (对于 1in11\le i\le n-1),而 ana_n 放置牌 a1a_1。这样排列后,牌的顺序就为 x1,x2,,xnx_1,x_2,\ldots ,x_n。然后,他把这种顺序排列的牌放入洗牌机洗牌 ss 次,得到牌的顺序为 p1,p2,,pnp_1,p_2,\ldots,p_n。现在,剀剀把牌的最后顺序和洗牌次数告诉凡凡,要凡凡猜出牌的最初顺序 x1,x2,,xnx_1,x_2,\ldots,x_n

输入格式

第一行为整数 nnss

第二行为牌的最终顺序 p1,p2,,pnp_1,p_2,\ldots,p_n

输出格式

为一行,即牌的最初顺序 x1,x2,,xnx_1,x_2,\ldots,x_n

5 2          
4 1 5 3 2

2 5 4 1 3

提示

数据规模与约定

对于 100%100\% 的数据,保证 1n,s1031\le n,s\le 10^3

数据保证,从 i=1i=1 开始,设第 ii 张牌上数是 jj,则赋值 i=ji=j 后继续此操作,最终会遍历所有牌。