分数: 600 点
问题陈述
N 硬币编号 0,1,\ldots,N-1 排列成一行。 最初,所有硬币都面朝上。 另外,你还会得到一个序列 A 长度 N 由之间的整数组成 0 和 N-1.
Snuke 将选择一个排列 p=(p_1,p_2,\ldots,p_N) of (1,\ldots,N) 以相同的概率执行 N 操作。 在 i-th (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 是正面朝上的硬币数量。
求期望值,模 998244353,Snuke 将收到的金额。
期望值模的定义 998244353
在这个问题中,我们可以证明所求的期望值始终是一个有理数。 此外,在该问题的约束下,当寻求的期望值表示为不可约分数时 \frac{y}{x},保证 x 不可整除 998244353.
然后,一个整数 z 之间 0 和 998244352 这样 xz \equiv y \pmod{998244353} 是唯一确定的。 找到这样的 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) or (2,1).
- If (1,2) 选择为 p:
在第一次操作中,硬币 0 被翻转,在第二次操作中,硬币 1 和硬币 0 被翻转。 一枚硬币,一枚硬币 0,结果面朝上,所以他收到 1 日元。
- If (2,1) 选择为 p:
在第一次操作中,硬币 0 和硬币 1 被翻转,在第二次操作中,硬币 1 被翻转。 一枚硬币,一枚硬币 1,结果面朝上,所以他收到 1 日元。
因此,他收到的钱的期望值为 1 日元。
示例输入 2
4 3 1 1 2
示例输出 2
665496237
打印期望值模 998244353.