Only Once

AtCoder

IDabc284_g

Time2000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

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$ [samples]

对于一个长度为 $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$。$A$ 可能的序列共有 $N^N$ 个。求对所有这些序列，$\displaystyle \sum_{i=1}^{N} S_i$ 的总和，并对 $M$ 取模。 ## Constraints * $1\leq N \leq 2\times 10^5$ * $10^8\leq M \leq 10^9$ * $N$ 和 $M$ 为整数。 ## Input 输入从标准输入给出，格式如下： $N$ $M$ [samples]

Samples

Input #1

4 100000000

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$.

Input #2

7 1000000000

Output #2

Input #3

2023 998244353

Output #3

737481389

Print the sum modulo $M$.

Input #4

100000 353442899

Output #4

271798911

API Response (JSON)

{
  "problem": {
    "name": "Only Once",
    "description": {
      "content": "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_",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc284_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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_...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "对于一个长度为 $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}})$ 如下。\n\n*   $B_{i,1}=i$.\n*   $B_{i,j+1}=A_{...",
      "is_translate": true,
      "language": "Chinese"
    }
  ]
}

Full JSON Raw Segments