← 返回题目列表

Codeforces · 2146/F

F. 冒泡排序

中文机器翻译题面 查看原题

你刚刚学习了算法 冒泡排序,能够以非降序对数组进行排序。让我们定义函数 $$$\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$$$的排列数$$$^{\text{*}}$$$ $$$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$$$ 成立。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$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\leq n\leq 10^6$$$, $$$0\leq m\leq 1000$$$)。

接下来是 $$$m$$$ 行,第 $$$i$$$ 行包含三个整数 $$$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$$$ 为模。

示例

输入
复制

6
4 3
0 1 1
1 3 3
2 4 4
3 2
0 3 3
1 2 3
4 3
1 2 2
2 3 4
0 1 2
5 3
1 1 4
3 5 5
4 5 5
10 5
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
1000000 0

输出
复制

2
1
8
80
192600
373341033

注意

在第一个测试用例中,只有排列 $$$[3,1,4,2]$$$ 和 $$$[4,1,3,2]$$$ 满足限制。以$$$[3,1,4,2]$$$为例。让我们计算数组$$$b$$$:

  • $$$\text{排序}([3])=0$$$;
  • $$$\text{排序}([3,1])=1$$$;
  • $$$\text{排序}([3,1,4])=1$$$;
  • $$$\text{排序}([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]$$$.