P15826 [JOI Open 2014] 太空海盗 / Space Pirate

在很久很久以前，在一个遥远的星系里……有 $N$ 颗高度文明的恒星，编号从 1 到 $N$。每颗恒星上都有一个传送门。每个传送门都有一个固定的目的地。我们只能沿着传送门的指向单向旅行。 银河帝国艺术博物馆会在星系中的恒星上举办艺术展。现在，展览正在恒星 1 上举行。下一场展览将在从恒星 1 出发，使用传送门旅行 $K$ 次后到达的恒星上举办。 太空警察发现，有个太空海盗计划窃取博物馆的藏品。这名海盗将入侵传送门系统，非法篡改恒星 $a$ 上传送门的目的地。恒星 $a$ 上传送门的目的地将被修改为恒星 $b$。该海盗只会入侵并修改一颗恒星的传送门系统。然而，太空警察无法确定 $a$ 和 $b$ 的具体值。 为了预测下一场展览的位置，太空警察希望知道，对于每个 $i$，有多少对 $(a, b)$ 使得下一场展览会在恒星 $i$ 举办。计算这些数值是一项艰巨的任务。鉴于你是一位优秀的程序员，太空警察请求你帮忙计算。 ### 任务 给定每个传送门的当前目的地，对于每个 $i$，计算有多少对 $(a, b)$ 使得下一场展览会在恒星 $i$ 举办。

从标准输入读取以下数据。 - 输入的第一行包含两个以空格分隔的整数 $N$ 和 $K$。这表示星系中有 $N$ 颗恒星，下一场展览将在从恒星 1 出发，使用传送门旅行 $K$ 次后到达的恒星上举办。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个整数 $A_i$（$1 \le A_i \le N$）。这表示当前恒星 $i$ 上传送门的目的地是恒星 $A_i$。

向标准输出写入 $N$ 行。第 $i$ 行（$1 \le i \le N$）应输出一个整数，表示使得下一场展览会在恒星 $i$ 举办的对 $(a, b)$ 的数量。

### 样例 1 解释 每个传送门的目的地如图 1 所示。 :::align{center}  图 1 ::: 如果 $(a, b) = (1, 4)$，恒星 1 上传送门的目的地会被篡改为恒星 4。每个传送门的目的地将变成如图 2 所示。若从恒星 1 出发，使用传送门旅行 7 次，我们将到达恒星 4。因此，下一场展览将在恒星 4 举办。（旅行路径为：$1 \to 4 \to 3 \to 4 \to 3 \to 4 \to 3 \to 4$）。 :::align{center}  ::: 有三对 $(a, b)$（即 $(1,4)$、$(2,4)$、$(5,3)$）使得下一场展览在恒星 4 举办。对于每对 $(a, b)$，下一场展览的位置总结如下表。 | $i$ | 使得下一场展览在恒星 $i$ 举办的对 $(a, b)$ | |:-:|:-:| | $1$ | $(1,1)$ | | $2$ | $(1,2)$、$(2,2)$ | | $3$ | $(1,3)$、$(2,3)$、$(5,4)$ | | $4$ | $(1,4)$、$(2,4)$、$(5,3)$ | | $5$ | $(1,5)$、$(2,1)$、$(2,5)$、$(3,1)$、$(3,2)$、$(3,3)$、$(3,4)$、$(3,5)$、$(4,1)$、$(4,2)$、$(4,3)$、$(4,4)$、$(4,5)$、$(5,1)$、$(5,2)$、$(5,5)$ | 在计数 $(a, b)$ 对的数量时，$a = b$ 的情况也应计入。此外，即使传送门目的地实际上未被改变（即修改前后的目的地相同），对应的对 $(a, b)$ 也应被计入。 ### 注意 - 恒星 $i$ 上传送门的目的地可以是恒星 $i$ 本身。在这种情况下，如果从恒星 $i$ 出发多次使用传送门，我们将一直停留在恒星 $i$。 - 即使恒星 $a$ 上传送门的当前目的地已经是恒星 $b$，太空海盗仍然可能入侵传送门系统并将目的地覆写为恒星 $b$。在这种情况下，恒星 $a$ 上传送门的目的地保持不变。在计算满足题目描述条件的 $(a, b)$ 对时，这类情况也应包含在内。 ### 约束条件 所有输入数据满足以下条件。 - $1 \le N \le 100000$。 - $N \le K \le 10^{18}$。 ### 子任务 #### 子任务 1 [10 分] - $N \le 100$。 #### 子任务 2 [37 分] - $N \le 3000$。 #### 子任务 3 [33 分] - 对于所有 $1 \le i < j \le N$，满足 $A_i \ne A_j$。 #### 子任务 4 [20 分] - 无额外约束。 翻译由 DeepSeek V3.2 完成