AT_arc178_f.[ARC178F] Long Sequence Inversion

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

给定正整数 $N$ 、 $M$ 、 $K$ 以及长度为 $M$ 的非负整数序列 $A = (A_0, A_1, \dots, A_{M-1})$ ，满足 $2^{N-1} \leq K < 2^N$ 。

在输入中， $K$ 以二进制表示为 $N$ 位的数字，其他整数以十进制表示。

另外，序列 $A$ 并未直接给出，而是通过以下方式描述：对于每个 $i=0, 1, \ldots, M-1$ ，提供长度为 $L_i$ 的整数序列 $X_i = (X_{i,0}, X_{i,1}, \dots, X_{i,L_i-1})$ ，使得 $A_i = \sum_{j=0}^{L_i-1} 2^{X_{i,j}}$ 。条件是 $0 \leq X_{i,0} < X_{i,1} < \cdots < X_{i,L_i-1} < N$ 。

我们的目标是计算由以下规律构成的长度为 $MK$ 的序列 $B = (B_0, B_1, \dots, B_{MK-1})$ 的逆序对数，并输出该值对 $998244353$ 取模的结果。

对于任意 $0 \leq a < K$ $0 \leq a < K$ 和任意 $0 \leq b < M$ $0 \leq b < M$ ，有：
- $B_{aM+b}$ 等于 $\operatorname{popcount}(a \operatorname{AND} A_b)$ 除以 $2$ 的余数。

其中，按位与运算符 $\operatorname{AND}$ 是怎样运算的？对整数 $A$ 和 $B$ ，其按位与运算 $A \operatorname{AND} B$ 在二进制表示下的第 $2^k$ 位（ $k \geq 0$ ）的值，当且仅当 $A$ 和 $B$ 在该位上均为 $1$ 时为 $1$ ，否则为 $0$ 。

例如， $3 \operatorname{AND} 5 = 1$ （二进制表示为 $011 \operatorname{AND} 101 = 001$ ）。不论先后顺序，多个整数按位与的结果是稳定的，可表达为 $(((p_1 \operatorname{AND} p_2) \operatorname{AND} \cdots) \operatorname{AND} p_k)$ 。

同时， $\operatorname{popcount}$ 函数作用于非负整数 $x$ ，返回其二进制表示中 $1$ 的总个数。具体来说，假设 $x = \sum_{i=0}^\infty b_i 2^i$ ，则 $\operatorname{popcount}(x) = \sum_{i=0}^\infty b_i$ 。举例来说， $13$ 在二进制下是 1101，因此 $\operatorname{popcount}(13) = 3$ 。

输入格式

从标准输入读取，格式如下：

$N$ $M$ $K$ $L_0$ $X_{0,0}$ $X_{0,1}$ $\cdots$ $X_{0,L_0-1}$ $L_1$ $X_{1,0}$ $X_{1,1}$ $\cdots$ $X_{1,L_1-1}$ $\ldots$ $L_{M-1}$ $X_{M-1,0}$ $X_{M-1,1}$ $\cdots$ $X_{M-1,L_{M-1}-1}$

输出格式

输出计算得到的逆序对数结果对 $998244353$ 取模的值。

输入输出样例

输入#1
```
2 4
11
1 0
2 0 1
0
1 1
```
输出#1
```
9
```
输入#2
```
3 3
101
2 1 2
2 0 1
1 0
```
输出#2
```
23
```

输入#3

16 7
1101010000100110
11 0 1 2 3 7 10 11 12 13 14 15
7 4 6 8 10 11 12 13
6 0 1 6 8 10 12
8 0 3 5 6 10 11 12 13
10 0 1 2 3 4 5 6 8 12 13
9 3 4 5 6 8 9 11 14 15
8 0 4 7 9 10 11 13 14

输出#3

97754354

输入#4

92 4
10101100101111111111011101111111101011001011111110011110111111101111111110100111100010111011
23 1 2 5 13 14 20 28 32 34 39 52 56 59 60 62 64 67 69 71 78 84 87 91
20 15 17 22 28 36 40 43 47 52 53 57 67 72 77 78 81 87 89 90 91
23 7 8 9 10 11 13 16 19 22 23 30 33 42 49 51 52 58 64 71 73 76 79 83
22 1 13 19 26 27 28 29 35 39 40 41 46 55 60 62 64 67 74 79 82 89 90

输出#4

291412708

说明/提示

$1 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$2^{N-1} \leq K < 2^N$
$0 \leq L_i \leq N$
$\sum L_i \leq 2 \times 10^5$
$0 \leq X_{i,0} < X_{i,1} < \cdots < X_{i,L_i-1} < N$
所有输入都是整数
$K$ 已经用二进制表示
除 $K$ 以外其他数以十进制表示

请输出对 $998244353$ 取模的逆序对数量。

本翻译由 AI 自动生成

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

首页