102846: [AtCoder]ABC284 G - Only Once

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

For a sequence of length $N$, $A = (A_1,A_2,\dots,A_N)$, consisting of integers between $1$ and $N$, inclusive, and an integer $i\ (1\leq i \leq N)$, let us define a sequence of length $10^{100}$, $B_i=(B_{i,1},B_{i,2},\dots,B_{i,10^{100}})$, as follows.

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

Additionally, let us define $S_i$ as the number of distinct integers that occur exactly once in the sequence $B_i$. More formally, $S_i$ is the number of values $k$ such that exactly one index $j\ (1\leq j\leq 10^{100})$ satisfies $B_{i,j}=k$.

You are given an integer $N$. There are $N^N$ sequences that can be $A$. Find the sum of $\displaystyle \sum_{i=1}^{N} S_i$ over all of them, modulo $M$.

Constraints

  • $1\leq N \leq 2\times 10^5$
  • $10^8\leq M \leq 10^9$
  • $N$ and $M$ are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

Output

Print the answer as an integer.


Sample Input 1

4 100000000

Sample Output 1

624

As an example, let us consider the case $A=(2,3,3,4)$.

  • For $i=1$: we have $B_1=(1,2,3,3,3,\dots)$, where two integers, $1$ and $2$, occur exactly once, so $S_1=2$.
  • For $i=2$: we have $B_2=(2,3,3,3,\dots)$, where one integer, $2$, occurs exactly once, so $S_2=1$.
  • For $i=3$: we have $B_3=(3,3,3,\dots)$, where no integers occur exactly once, so $S_3=0$.
  • For $i=4$: we have $B_4=(4,4,4,\dots)$, where no integers occur exactly once, so $S_4=0$.

Thus, we have $\displaystyle \sum_{i=1}^{N} S_i=2+1+0+0=3$.

If we similarly compute $\displaystyle \sum_{i=1}^{N} S_i$ for the other $255$ sequences, the sum of this value over all $256$ sequences is $624$.


Sample Input 2

7 1000000000

Sample Output 2

5817084

Sample Input 3

2023 998244353

Sample Output 3

737481389

Print the sum modulo $M$.


Sample Input 4

100000 353442899

Sample Output 4

271798911

Input

题意翻译

给定 $n$,对于一个长度为 $n$,值域为 $n$ 的序列 $A$,按如下方法构造无限序列 $B_i(1 \le i \le n)$: - $B_{i,1} = i$ - $B_{i,j} = A_{B_{i,j-1}}(j > 1)$ 记 $S_i$ 为 $B_i$ 中只出现了一次的元素的个数,定义序列 $A$ 的价值为 $\sum_{i=1}^n S_i$,现在请求出所有 $n^n$ 个可能的序列 $A$ 的价值之和对 $M$ 取模的结果。 $n \le 2 \times 10^5, 10^8 \le M \le 10^9$.

Output

得分:$600$分

问题描述

给定一个长度为$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$是满足以下条件的值$k$的数量:恰好有一个索引$j\ (1\leq j\leq 10^{100})$使得$B_{i,j}=k$。

给你一个整数$N$。可以构成$A$的序列有$N^N$个。求它们中所有$\displaystyle \sum_{i=1}^{N} S_i$的和模$M$。

约束

  • $1\leq N \leq 2\times 10^5$
  • $10^8\leq M \leq 10^9$
  • $N$和$M$是整数。

输入

输入通过标准输入给出,格式如下:

$N$ $M$

输出

打印答案作为整数。


样例输入1

4 100000000

样例输出1

624

作为例子,让我们考虑$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$。


样例输入2

7 1000000000

样例输出2

5817084

样例输入3

2023 998244353

样例输出3

737481389

打印结果模$M$。


样例输入4

100000 353442899

样例输出4

271798911

加入题单

上一题 下一题 算法标签: