B - 01 Inversion Expected Editorial /

Time Limit: 2 sec / Memory Limit: 2048 MB

配点 : 1000 点

問題文

0, 1 からなる長さ N の文字列 S が与えられます． 整数の組 (i,j) (1 \leq i < j \leq N) であって，S の i 文字目が 1, j 文字目が 0 であるようなものを転倒ペアと呼ぶことにします．

S 内に転倒ペアが存在する限り，以下の操作を行います．

  • 転倒ペア (i,j) をランダムに一つ選ぶ．選択はこれ以前の選択と独立で，かつ一様ランダムであるとする． そして，S の i 文字目と j 文字目を入れ替える．

操作回数の期待値を \text{mod }{998244353} で求めてください．

期待値 \text{mod }{998244353} の定義

求める期待値は必ず有理数になることが証明できます． また，この問題の制約のもとでは，その値を既約分数 \frac{P}{Q} で表した時，Q \neq 0 \pmod{998244353} となることも証明できます． よって，R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります． この R を答えてください．

制約

  • 1 \leq N \leq 250000
  • S は 0, 1 からなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる．

N
S

出力

答えを出力せよ．

入力例 1

2
10

出力例 1

1

操作回数の期待値は 1 です．

入力例 2

3
110

出力例 2

499122178

操作回数の期待値は 3/2 です．

入力例 3

1
0

出力例 3

0

入力例 4

10
1011000010

出力例 4

133099253

入力例 5

100
0101110010001000111000111001001101001100000111110001010010001010101100011001011011101101100001100111

出力例 5

407907276

Score : 1000 points

Problem Statement

You are given a string S of length N consisting of 0 and 1. We define an inversion pair as a pair of integers (i, j) (1 \leq i < j \leq N) such that the i-th character of S is 1 and the j-th character of S is 0.

As long as there is an inversion pair in S, perform the following operation:

  • Randomly choose an inversion pair (i, j). The choice is independent of previous choices and is uniformly random. Then, swap the i-th and j-th characters of S.

Find the expected number of operations, modulo 998244353.

What is the expected value modulo 998244353?

It can be proved that the sought expected value is always rational. Moreover, under the constraints of this problem, it can be proved that if the expected value is expressed as an irreducible fraction \frac{P}{Q}, then Q \neq 0 \pmod{998244353}. Thus, there exists a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Report this R.

Constraints

  • 1 \leq N \leq 250000
  • S is a string of length N consisting of 0 and 1.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

2
10

Sample Output 1

1

The expected number of operations is 1.

Sample Input 2

3
110

Sample Output 2

499122178

The expected number of operations is 3/2.

Sample Input 3

1
0

Sample Output 3

0

Sample Input 4

10
1011000010

Sample Output 4

133099253

Sample Input 5

100
0101110010001000111000111001001101001100000111110001010010001010101100011001011011101101100001100111

Sample Output 5

407907276