P15064 [UOI 2024 II Stage] Everyone Loves Permutations

一个长度为 $n$ 的排列是一个包含 $1$ 到 $n$ 所有整数的数组，且其所有元素两两不同。 Anton 在成长过程中玩过各种数组后，转向研究更有趣的数组——排列。在撰写论文时，他遇到了一个非常困难的问题。 他有一个长度为 $n$ 的排列 $p$ 和一个整数 $k$。他决定构建一个大小为 $(k+1) \times n$ 的二维数组 $a$。 - 对所有 $j$（$1 \leq j \leq n$），$a_{0j}=j$； - 对所有 $i$（$1 \leq i \leq k$）和 $j$（$1 \leq j \leq n$），$a_{ij}=a_{(i-1)p_j}$。 设 $p=[5, 3, 1, 4, 2]$ 且 $k=3$，则我们得到以下数组。 $$ \begin{array}{|c|c|c|c|c|c|} \hline a_{ij} & j=1 & j=2 & j=3 & j=4 & j=5 \\ \hline\hline i=0 & 1 & 2 & 3 & 4 & 5 \\ \hline i=1 & 5 & 3 & 1 & 4 & 2 \\ \hline i=2 & 2 & 1 & 5 & 4 & 3 \\ \hline i=3 & 3 & 5 & 2 & 4 & 1 \\ \hline \end{array} $$ 对于每个 $x$（$1 \leq x \leq n$），他想知道所有满足 $a_{ij}=x$ 的 $j$ 之和，其中 $1 \leq i \leq k$。换句话说，他想求 $k$ 个数的和——即 $x$ 在每个 $a_i$ 中的索引。 考虑上一个例子。如果 $x=1$，答案将是 $3+2+5=10$。 经过一番思考和简单思路，Anton 很快解决了这个问题。现在他想看看你是否也能解决它。

输入的第一行包含两个整数 $n$、$k$（$1 \le n \le 10^6$，$1 \le k \le 10^9$）——分别表示排列的长度和操作重复的次数。 第二行包含排列 $p$（$1 \le p_i \le n$）。

输出 $n$ 个整数，其中第 $i$ 个数是 $x=i$ 的答案。

- （$8$ 分）：$k = 1$； - （$17$ 分）：$p_i = i$； - （$26$ 分）：$n \le 2000, k \le 2000$； - （$28$ 分）：$n \le 2000$，且对任意 $i$ 和 $j$，存在 $k$ 使得 $p[p[p \dots p[i] \dots ]]=j$，其中嵌套进行 $k$ 次； - （$9$ 分）：对任意 $i$ 和 $j$，存在 $k$ 使得 $p[p[p \dots p[i] \dots ]]=j$，其中嵌套进行 $k$ 次； - （$12$ 分）：无额外限制。 翻译由 DeepSeek V3 完成