AT_abc284_g [ABC284G] Only Once

题目描述

给定一个由 $1$ 到 $N$ 之间的整数构成、长度为 $N$ 的数列 $A = (A_1, A_2, \dots, A_N)$，以及整数 $i\ (1 \leq i \leq N)$，定义长度为 $10^{100}$ 的数列 $B_i = (B_{i,1}, B_{i,2}, \dots, B_{i,10^{100}})$，其定义如下：

• $B_{i,1} = i$
• $B_{i,j+1} = A_{B_{i,j}} \quad (1 \leq j < 10^{100})$

此外，定义 $S_i$ 为“数列 $B_i$ 中恰好只出现一次的数的种类数”。更严格地说，$S_i$ 是满足“存在唯一的 $j\ (1 \leq j \leq 10^{100})$ 使得 $B_{i,j} = k$”的 $k$ 的个数。

给定整数 $N$。数列 $A$ 的所有可能情况共有 $N^N$ 种。对于所有这些 $A$，计算 $\displaystyle\sum_{i=1}^{N} S_i$，并将其总和对 $M$ 取余，输出结果。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$

输出格式

请输出答案的整数值。

输入输出样例 #1

输入 #1

4 100000000

输出 #1

624

输入输出样例 #2

输入 #2

7 1000000000

输出 #2

5817084

输入输出样例 #3

输入 #3

2023 998244353

输出 #3

737481389

输入输出样例 #4

输入 #4

100000 353442899

输出 #4

271798911

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $10^8 \leq M \leq 10^9$
• $N, M$ 均为整数

样例解释 1

以 $A = (2, 3, 3, 4)$ 为例：

• 当 $i=1$ 时：$B_1 = (1, 2, 3, 3, 3, \dots)$，只出现一次的数有 $1, 2$ 共 $2$ 个，因此 $S_1 = 2$。
• 当 $i=2$ 时：$B_2 = (2, 3, 3, 3, \dots)$，只出现一次的数为 $2$，因此 $S_2 = 1$。
• 当 $i=3$ 时：$B_3 = (3, 3, 3, \dots)$，没有只出现一次的数，因此 $S_3 = 0$。
• 当 $i=4$ 时：$B_4 = (4, 4, 4, \dots)$，没有只出现一次的数，因此 $S_4 = 0$。

所以，$\displaystyle\sum_{i=1}^{N} S_i = 2 + 1 + 0 + 0 = 3$。

对其他 $255$ 种 $A$ 也同样计算 $\displaystyle\sum_{i=1}^{N} S_i$，所有 $256$ 种情况的总和为 $624$。

样例解释 3

请输出总和对 $M$ 取余的结果。

由 ChatGPT 4.1 翻译