Only Once

题目描述

对于长度为 $N$ 的序列 $A = (A_1,A_2,\dots,A_N)$，其元素为 $1$ 到 $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}}\ (1\leq j<10^{100})。

另外，令 $S_i$ 为在序列 $B_i$ 中恰好出现一次的不同整数的个数。 更正式地，$S_i$ 是满足恰有一个下标 $j\ (1\leq j\leq 10^{100})$ 使得 $B_{i,j}=k$ 的值 $k$ 的个数。 给定整数 $N$。共有 $N^N$ 个可能的序列 $A$。求在所有这些序列上 $\displaystyle \sum_{i=1}^{N} S_i$ 的和，对 $M$ 取模后的结果。

输入格式

输入由标准输入提供，格式如下： $N$ $M$

输出格式

输出一个整数，表示答案。

4 100000000

624

7 1000000000

5817084

2023 998244353

737481389

100000 353442899

271798911

提示

$1\leq N \leq 2\times 10^5$ $10^8\leq M \leq 10^9$ $N$ 和 $M$ 为整数。例如，考虑 $A=(2,3,3,4)$。

对于 $i=1$：我们有 $B_1=(1,2,3,3,3,\dots)$，其中有两个整数 $1$ 和 $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$ 个序列同样计算 $\displaystyle \sum_{i=1}^{N} S_i$，在所有 $256$ 个序列上的该值之和为 $624$。
对 $M$ 取模后输出结果。

标签: AtCoder|abc284G

来源

AtCoder|abc284G