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

输入 #1

2
0 1

输出 #1

1

输入输出样例 #2

输入 #2

4
3 1 1 2

输出 #2

665496237

说明/提示

约束

• $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 翻译