← 返回题目列表

AtCoder · awtf2024_b

B. 01 预计反转

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

分数: 1000 点

问题陈述

给你一个字符串 S 长度 N 组成 0 和 1。 我们定义一个 反转对 作为一对整数 (i, j) (1 \leq i < j \leq N)使得 i- 第一个字符 S is 1 和 j- 第一个字符 S is 0.

只要有反转对 S,执行以下操作:

  • 随机选择一个反演对 (i, j)。该选择独立于先前的选择并且是一致随机的。 然后,交换 i-th 和 j- 第一个字符 S.

求预期运算次数,取模 998244353.

期望值模是多少 998244353?

可以证明,所求的期望值总是有理数。而且,在这个问题的约束下,可以证明,如果期望值表示为不可约分数 \frac{P}{Q},然后 Q \neq 0 \pmod{998244353}。因此,存在一个唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。报告此事 R.

约束

  • 1 \leq N \leq 250000
  • S 是一个长度为的字符串 N 组成 0 和 1.

输入

输入由标准输入按以下格式给出:

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