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