AT_abc272_h [ABC272Ex] Flipping Coins 2

有 $N$ 枚编号为 $0,1,\ldots,N-1$ 的硬币排成一排。开始时，所有硬币都是正面朝上。同时，给定一个长度为 $N$ 的数列 $A$，其中每个元素都是 $0$ 到 $N-1$ 之间的整数。 すぬけ君会等概率地选择一个 $1$ 到 $N$ 的排列 $p=(p_1,p_2,\ldots,p_N)$，然后进行 $N$ 次操作。第 $i$ 次操作（$1\leq i \leq N$）如下： - 翻转编号为 $(i-1)\bmod N$、$(i-1+1)\bmod N$、$\ldots$、$(i-1+A_{p_i})\bmod N$ 的 $(A_{p_i}+1)$ 枚硬币。 经过 $N$ 次操作后，记正面朝上的硬币数为 $k$，すぬけ君会从妈妈那里得到 $k$ 日元。 请你计算すぬけ君最终能获得的钱的期望值，并对 $998244353$ 取模输出。 期望值 $\bmod\ 998244353$ 的定义：本题中要求的期望值一定是有理数，并且在本题的约束下，若将期望值表示为最简分数 $\frac{y}{x}$，则 $x$ 一定不能被 $998244353$ 整除。 此时，存在唯一的 $0$ 到 $998244352$ 之间的整数 $z$，满足 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。

输入通过标准输入给出，格式如下： > $N$ $A_1$ $A_2$ $\ldots$ $A_N$

请输出答案。

## 约束 - $1 \leq N \leq 2\times 10^5$ - $0 \leq A_i \leq N-1$ - 输入均为整数 ## 样例解释 1 $p$ 可能为 $(1,2)$ 或 $(2,1)$。 - 当 $p=(1,2)$ 时，第 1 次操作翻转硬币 $0$，第 2 次操作翻转硬币 $1$ 和 $0$。最终只有硬币 $0$ 是正面朝上，因此得到 $1$ 日元。 - 当 $p=(2,1)$ 时，第 1 次操作翻转硬币 $0$ 和 $1$，第 2 次操作翻转硬币 $1$。最终只有硬币 $1$ 是正面朝上，因此得到 $1$ 日元。 因此，最终能获得的钱的期望值为 $1$ 日元。 ## 样例解释 2 请对期望值 $\bmod\ 998244353$ 输出答案。 由 ChatGPT 4.1 翻译