← 返回题目列表

AtCoder · abc272_h

Ex. 翻转硬币 2

中文机器翻译题面 查看原题

分数: 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.