AT_awtf2024_b.01 Inversion Expected

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个由 0 和 1 组成的长度为 $N$ 的字符串 $S$ 。对于满足 $1 \leq i < j \leq N$ ，且 $S$ 的第 $i$ 个字符为 1，第 $j$ 个字符为 0 的整数对 $(i, j)$ ，我们称其为逆序对。

只要 $S$ 中存在逆序对，就进行如下操作：

随机选择一个逆序对 $(i, j)$ 。每次选择都是独立且等概率的。然后交换 $S$ 的第 $i$ 个字符和第 $j$ 个字符。

请计算操作次数的期望值，并对 $998244353$ 取模后输出。

期望值 $\bmod\ 998244353$ 的定义：可以证明所求期望值一定是有理数。在本题的约束下，将其表示为最简分数 $\frac{P}{Q}$ 时， $Q \not\equiv 0 \pmod{998244353}$ 也可以保证。因此，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$ 。请输出 $R$ 。

输入格式

输入以以下格式从标准输入读入。

$N$ $S$

输出格式

请输出答案。

输入输出样例

输入#1
```
2
10
```
输出#1
```
1
```
输入#2
```
3
110
```
输出#2
```
499122178
```
输入#3
```
1
0
```
输出#3
```
0
```
输入#4
```
10
1011000010
```
输出#4
```
133099253
```

输入#5

100
0101110010001000111000111001001101001100000111110001010010001010101100011001011011101101100001100111

输出#5

407907276

说明/提示

限制

$1 \leq N \leq 250000$
$S$ 是由 0 和 1 组成的长度为 $N$ 的字符串

样例解释 1

操作次数的期望值为 $1$ 。

样例解释 2

操作次数的期望值为 $3/2$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页