AT_1_ttpc2024_1_l.Long Sequence Inversion 2

省选/NOI-

通过率：0%

AC君温馨提醒

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

题目描述

在这道题目中，「长度为 $ K $ 的排列」指的是「从 $ 0 $ 到 $ K - 1 $ 的所有数字所组成的一个排列」。此外，我们用 $ X[k] $ 来表示数列 $ X $ 的第 $ k $ 个元素（从 $ 0 $ 开始计数）。

现在给你一个长度为 $ L $ 的排列 $ P $，以及 $ L $ 个分别长度为 $ B $ 的排列 $ V_{0}, V_{1}, \dots, V_{L-1} $。我们定义一个长度为 $ B^L $ 的数列 $ A $，定义方式如下：

对于每个 $ 0 \leq n < B^L $，将 $ n $ 用 $ B $ 进制表示为 $ L $ 位数，记每一位的值为 $ N[i] $，即 $ n = N[0] B^{L-1} + N[1] B^{L-2} + \cdots + N[L-1] B^0 $，那么

$A[n] = \sum_{i=0}^{L-1} V_i[N[i]] \times B^{P[i]}$

你的任务是计算数列 $ A $ 的逆序对个数，并输出其对 $ 998244353 $ 取模的结果。

输入格式

输入通过标准输入流给出，格式如下：

$ L $ $ B $ $ P[0] $ $ P[1] $ $\cdots$ $ P[L-1] $ $ V_{0}[0] $ $ V_{0}[1] $ $\cdots$ $ V_{0}[B-1] $ $\vdots$ $ V_{L-1}[0] $ $ V_{L-1}[1] $ $\cdots$ $ V_{L-1}[B-1] $

输出格式

输出结果。

输入输出样例

输入#1
```
3 2
2 0 1
1 0
1 0
0 1
```
输出#1
```
14
```
输入#2
```
2 4
1 0
2 0 3 1
1 2 3 0
```
输出#2
```
60
```

输入#3

9 10
2 5 7 3 8 1 4 6 0
9 2 4 0 1 6 7 3 5 8
4 1 6 7 8 0 5 9 2 3
1 9 2 4 6 8 5 7 0 3
9 0 8 2 5 1 6 7 3 4
1 6 0 7 3 9 2 4 5 8
4 5 2 9 1 6 7 3 0 8
7 0 5 6 1 9 2 4 3 8
3 2 1 6 7 0 8 9 4 5
9 2 4 3 5 8 0 6 7 1

输出#3

138876070

说明/提示

所有输入都是整数。
$ 1 \leq L $
$ 2 \leq B $
$ L \times (B + 1) \leq 5 \times 10^5 $
$ P $ 是长度为 $ L $ 的排列。
对每个 $ 0 \leq i < L $，$ V_i $ 是长度为 $ B $ 的排列。

示例解释 1

例如，当 $ n = 5 $ 时，其在 $ B = 2 $ 进制下的表示为三位数 $ (1, 0, 1) $，那么：

$A[5] = V_{0}[1] \times 2^{P[0]} + V_{1}[0] \times 2^{P[1]} + V_{2}[1] \times 2^{P[2]} = 3$

用相同的方法计算得到 $ A = (5, 1, 4, 0, 7, 3, 6, 2) $。然后，计算出数列 $ A $ 的逆序对数量为 $ 14 $，所以输出 $ 14 $。

示例解释 2

同理可以计算出 $ A = (9, 1, 13, 5, 10, 2, 14, 6, 11, 3, 15, 7, 8, 0, 12, 4) $。数列 $ A $ 的逆序对数量是 $ 60 $，所以输出 $ 60 $。

说明

记得计算结果需对 $ 998244353 $ 取模。

本翻译由 AI 自动生成

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

首页