翻硬币 2

题目描述

编号为 $0,1,\ldots,N-1$ 的 $N$ 枚硬币排成一排。最初,所有硬币都是正面朝上。此外,给你一个长度为 $N$、由 $0$ 到 $N-1$ 之间的整数组成的序列 $A$。

Snuke 将以等概率选择一个 $(1,\ldots,N)$ 的排列 $p=(p_1,p_2,\ldots,p_N)$,并执行 $N$ 次操作。在第 $i$ 次操作 $(1 \le i \le 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$。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

样例

2
0 1

1

$p$ 可以是 $(1,2)$ 或 $(2,1)$。

如果选择 $(1,2)$ 作为 $p$:

在第一次操作中,翻转硬币 0;在第二次操作中,翻转硬币 1 和硬币 0。结果有 1 枚硬币(硬币 0)正面朝上,所以他得到 1 日元。

如果选择 $(2,1)$ 作为 $p$:

在第一次操作中,翻转硬币 0 和硬币 1;在第二次操作中,翻转硬币 1。结果有 1 枚硬币(硬币 1)正面朝上,所以他得到 1 日元。

因此,他得到的钱的期望值是 1 日元。

4
3 1 1 2

665496237

输出期望值对 $998244353$ 取模的值。

数据范围

• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le N-1$
• 输入中的所有值均为整数。