/ 
Time Limit: 10 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
0,1,\ldots,N-1 の番号がついた N 枚のコインが並べられています。はじめ、全てのコインは表を向いています。また、 0 以上 N-1 以下の整数からなる長さ N の数列 A が与えられます。
すぬけ君は (1,\ldots,N) を並び替えて得られる順列 p=(p_1,p_2,\ldots,p_N) を等確率で 1 つ選び 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 円もらえます。
すぬけ君が得られるお金の期待値を \text{mod } 998244353 で求めてください。
期待値 \text{mod } 998244353 の定義
この問題で求める期待値は必ず有理数になることが証明できます。 また、この問題の制約下では、求める期待値を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。
このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この 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) と (2,1) です。
- p として (1,2) が選ばれたとき
1 回目の操作ではコイン 0 をひっくり返します。 2 回目の操作ではコイン 1 とコイン 0 をひっくり返します。最終的に表向きのコインはコイン 0 の 1 枚なので、1 円もらえます。
- p として (2,1) が選ばれたとき
1 回目の操作ではコイン 0 とコイン 1 をひっくり返します。 2 回目の操作ではコイン 1 をひっくり返します。最終的に表向きのコインはコイン 1 の 1 枚なので、1 円もらえます。
以上より、得られるお金の期待値は 1 円 です。
入力例 2
4 3 1 1 2
出力例 2
665496237
期待値を \text{mod } 998244353 で出力してください。
Score : 600 points
Problem Statement
N coins numbered 0,1,\ldots,N-1 are arranged in a row. Initially, all coins are face up. Also, you are given a sequence A of length N consisting of integers between 0 and N-1.
Snuke will choose a permutation p=(p_1,p_2,\ldots,p_N) of (1,\ldots,N) at equal probability and perform N operations. In the i-th (1\leq i \leq N) operation,
- he flips (A_{p_i}+1) coins: coin (i-1) \bmod N, coin (i-1+1 ) \bmod N, \ldots, and coin (i -1+ A_{p_i}) \bmod N.
After the N operations, Snuke receives k yen (the currency in Japan) from his mother, where k is the number of face-up coins.
Find the expected value, modulo 998244353, of the money Snuke will receive.
Definition of expected value modulo 998244353
In this problem, we can prove that the sought expected value is always a rational number. Moreover, under the Constraints of this problem, when the sought expected value is represented as an irreducible fraction \frac{y}{x}, it is guaranteed that x is indivisible by 998244353.
Then, an integer z between 0 and 998244352 such that xz \equiv y \pmod{998244353} is uniquely determined. Find such z.
Constraints
- 1 \leq N\leq 2\times 10^5
- 0\leq A_i \leq N-1
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
2 0 1
Sample Output 1
1
p can be either (1,2) or (2,1).
- If (1,2) is chosen as p:
In the first operation, coin 0 is flipped, and in the second operation, coin 1 and coin 0 are flipped. One coin, coin 0, results in being face up, so he receives 1 yen.
- If (2,1) is chosen as p:
In the first operation, coin 0 and coin 1 are flipped, and in the second operation, coin 1 is flipped. One coin, coin 1, results in being face up, so he receives 1 yen.
Therefore, the expected value of the money he receives is 1 yen.
Sample Input 2
4 3 1 1 2
Sample Output 2
665496237
Print the expected value modulo 998244353.