AT_abc367_e.[ABC367E] Permute K times

普及+/提高

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给定一个每个元素都在 11 到 NN 之间的长度为 NN 的序列 XX 和一个长度为 NN 的序列 AA。请输出对序列 AA 执行以下操作 KK 次后的结果:

  • 构造一个新的序列 BB,其中 Bi=AXiB_i = A_{X_i},然后将 BB 设为新的 AA。

输入格式

输入以以下格式从标准输入给出:

NN KK X1X_1 X2X_2 …\ldots XNX_N A1A_1 A2A_2 …\ldots ANA_N

输出格式

设操作后的 AA 为 A′A',请以以下格式输出:

A1′A'_1 A2′A'_2 …\ldots AN′A'_N

输入输出样例

  • 输入#1

    7 3
    5 2 6 3 1 4 6
    1 2 3 5 7 9 11

    输出#1

    7 2 3 5 1 9 3
  • 输入#2

    4 0
    3 4 1 2
    4 3 2 1

    输出#2

    4 3 2 1
  • 输入#3

    9 1000000000000000000
    3 7 8 5 9 3 7 4 2
    9 9 8 2 4 4 3 5 3

    输出#3

    3 3 3 3 3 3 3 3 3

说明/提示

制约条件

  • 所有输入都是整数。
  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 0≤K≤10180 \le K \le 10^{18}
  • 1≤Xi≤N1 \le X_i \le N
  • 1≤Ai≤2×1051 \le A_i \le 2 \times 10^5

示例解释 1

在这个例子中,X=(5,2,6,3,1,4,6)X = (5, 2, 6, 3, 1, 4, 6),操作前的序列 A=(1,2,3,5,7,9,11)A = (1, 2, 3, 5, 7, 9, 11)。

  • 执行一次操作后,序列变为 (7,2,9,3,1,5,9)(7, 2, 9, 3, 1, 5, 9)。
  • 执行两次操作后,序列变为 (1,2,5,9,7,3,5)(1, 2, 5, 9, 7, 3, 5)。
  • 执行三次操作后,序列变为 (7,2,3,5,1,9,3)(7, 2, 3, 5, 1, 9, 3)。

示例解释 2

也可能不会执行任何操作。

输入解题思路,AI测评打分。不知道怎么写?

首页