102727: [AtCoder]ABC272 Ex - Flipping Coins 2
Description
Score : $600$ points
Problem Statement
$N$ coins numbered $0,1,\ldots,N-1$ are arranged in a row. Initially, all coins are face up. Also, you are given a sequence $A$ of length $N$ consisting of integers between $0$ and $N-1$.
Snuke will choose a permutation $p=(p_1,p_2,\ldots,p_N)$ of $(1,\ldots,N)$ at equal probability and perform $N$ operations. In the $i$-th $(1\leq i \leq N)$ operation,
- he flips $(A_{p_i}+1)$ coins: coin $(i-1) \bmod N$, coin $(i-1+1 ) \bmod N$, $\ldots$, and coin $(i -1+ A_{p_i}) \bmod N$.
After the $N$ operations, Snuke receives $k$ yen (the currency in Japan) from his mother, where $k$ is the number of face-up coins.
Find the expected value, modulo $998244353$, of the money Snuke will receive.
Definition of expected value modulo $998244353$
In this problem, we can prove that the sought expected value is always a rational number. Moreover, under the Constraints of this problem, when the sought expected value is represented as an irreducible fraction $\frac{y}{x}$, it is guaranteed that $x$ is indivisible by $998244353$.
Then, an integer $z$ between $0$ and $998244352$ such that $xz \equiv y \pmod{998244353}$ is uniquely determined. Find such $z$.
Constraints
- $1 \leq N\leq 2\times 10^5$
- $0\leq A_i \leq N-1$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print the answer.
Sample Input 1
2 0 1
Sample Output 1
1
$p$ can be either $(1,2)$ or $(2,1)$.
- If $(1,2)$ is chosen as $p$:
In the first operation, coin $0$ is flipped, and in the second operation, coin $1$ and coin $0$ are flipped. One coin, coin $0$, results in being face up, so he receives $1$ yen.
- If $(2,1)$ is chosen as $p$:
In the first operation, coin $0$ and coin $1$ are flipped, and in the second operation, coin $1$ is flipped. One coin, coin $1$, results in being face up, so he receives $1$ yen.
Therefore, the expected value of the money he receives is $1$ yen.
Sample Input 2
4 3 1 1 2
Sample Output 2
665496237
Print the expected value modulo $998244353$.
Input
题意翻译
$N$ 枚硬币排成一列，依次编号为 $0,1,\cdots,N-1$，初始均为正面朝上。 给定长为 $N$ 的序列 $A$ 满足 $A$ 中元素为 $0 \sim N-1$ 的整数。随机选取一个 $1,2,\cdots,N$ 的排列 $p_1,\cdots,p_N$，对每个 $i=1,2,\cdots,N$，依次翻动第 $(i-1) \bmod N,(i-1+1) \bmod N,\cdots,(i-1+A_{p_i}) \bmod N$ 枚硬币。 求操作完成后正面朝上的硬币数量期望，答案对 $998244353$ 取模。Output
问题描述
将编号为$0,1,\ldots,N-1$的$N$枚硬币排成一排。最初，所有的硬币都是正面朝上的。此外，你还将得到一个由$0$到$N-1$之间的整数组成的长度为$N$的序列$A$。
Snuke将以相等的概率选择一个$(1,\ldots,N)$的排列$p=(p_1,p_2,\ldots,p_N)$并执行$N$次操作。在第$i$次$(1\leq i \leq N)$操作中，
- 他将翻转$(A_{p_i}+1)$枚硬币：第$(i-1) \bmod N$枚硬币，第$(i-1+1 ) \bmod N$枚硬币，$\ldots$，第$(i -1+ A_{p_i}) \bmod N$枚硬币。
在执行完$N$次操作后，Snuke的母亲将给他$ k $日元（日本的货币），其中$k$是正面朝上的硬币的数量。
求Snuke将收到的金钱的期望值（对$998244353$取模）。
对$998244353$取模的期望值定义
在这个问题中，我们可以证明所求期望值总是有理数。 此外，在本问题的约束下，当所求期望值表示为不可约分数$\frac{y}{x}$时，可以保证$x$能够被$998244353$整除。
那么，满足$xz \equiv y \pmod{998244353}$的介于$0$和$998244352$之间的整数$z$是唯一确定的。找到这样的$z$。
约束
- $1 \leq N\leq 2\times 10^5$
- $0\leq A_i \leq N-1$
- 输入中的所有值都是整数。
输入
输入数据从标准输入按以下格式给出：
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
输出
打印答案。
样例输入1
2 0 1
样例输出1
1
$p$可以是$(1,2)$或$(2,1)$。
- 如果选择$(1,2)$作为$p$：
在第一次操作中，翻转第$0$枚硬币，在第二次操作中，翻转第$1$枚硬币和第$0$枚硬币。结果正面朝上的硬币是第$0$枚硬币，所以他收到$1$日元。
- 如果选择$(2,1)$作为$p$：
在第一次操作中，翻转第$0$枚硬币和第$1$枚硬币，在第二次操作中，翻转第$1$枚硬币。结果正面朝上的硬币是第$1$枚硬币，所以他收到$1$日元。
因此，他收到的金钱的期望值为$1$日元。
样例输入2
4 3 1 1 2
样例输出2
665496237
打印对$998244353$取模的期望值。