CF2146F Bubble Sort

你刚刚学习了冒泡排序算法，它可以将一个数组按非降序排序。我们定义函数 $\text{sort}(a)$ 如下伪代码： ``` function sort(array a): rounds := 0 n := length of a while a is not non-decreasing: rounds := rounds + 1 for i from 1 to n - 1: if a[i] > a[i + 1]: swap(a[i], a[i + 1]) return rounds ``` 如上所示，$\text{sort}(a)$ 的返回值表示通过冒泡排序将数组 $a$ 排序为非降序所需的轮数。 现给定一个整数 $n$，以及 $m$ 个三元组 $(k_i, l_i, r_i)$（$1 \le i \le m$）。请统计满足以下限制条件的长度为 $n$ 的排列 $p$ 的个数，答案对 $998\,244\,353$ 取模： - 对于每个 $1 \le i \le n$，令 $b_i = \text{sort}([p_1, p_2, \ldots, p_i])$； - 对于每个 $1 \le j \le m$，令 $x$ 表示有多少个索引 $y$（$1 \le y \le n$）满足 $b_y \le k_j$，则一定有 $l_j \le x \le r_j$。 注：排列是长度为 $n$ 的数组，包含 $1$ 到 $n$ 的所有整数且互不重复。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$，但包含 $4$）。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。 每组测试数据的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^6$，$0 \le m \le 1000$）。 随后 $m$ 行，每行三个整数 $k_i, l_i, r_i$（$0 \le k_i \le n-1$，$1 \le l_i \le r_i \le n$），表示限制条件。 保证所有测试数据中 $m^2$ 的总和不超过 $10^6$。

对于每组测试数据，输出一个整数，表示满足条件的排列数，对 $998\,244\,353$ 取模。

在第一个测试点中，只有排列 $[3,1,4,2]$ 和 $[4,1,3,2]$ 满足条件。以下以 $[3,1,4,2]$ 为例，计算其 $b$ 数组： - $\text{sort}([3])=0$； - $\text{sort}([3,1])=1$； - $\text{sort}([3,1,4])=1$； - $\text{sort}([3,1,4,2])=2$。 因而 $b=[0,1,1,2]$，满足所有限制。 第一个测试用例只有排列 $[1,2,3]$ 满足条件。 第三个测试用例有 $8$ 个排列满足条件： - $[2,3,1,4]$； - $[2,4,1,3]$； - $[3,2,1,4]$； - $[3,4,1,2]$； - $[3,4,2,1]$； - $[4,2,1,3]$； - $[4,3,1,2]$； - $[4,3,2,1]$。 由 ChatGPT 5 翻译