← 返回题目列表

Codeforces · 1558/D

D. 一流的插入

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

考虑用于以非递减顺序对长度为 $$$n$$$ 的整数序列 $$$[a_1, a_2, \ldots, a_n]$$$ 进行排序的插入排序算法。

对于从 $$$2$$$ 到 $$$n$$$ 的每个 $$$i$$$,执行以下操作。如果 $$$a_i \ge a_{i-1}$$$,则不执行任何操作并继续执行 $$$i$$$ 的下一个值。否则,找到最小的$$$j$$$,使得$$$a_i < a_j$$$,将$$$j$$$到$$$i-1$$$位置上的元素向右移动一位,并记下$$$a_i$$$的初始值到位置$$$j$$$。在这种情况下,我们会说我们执行了从位置 $$$i$$$ 到位置 $$$j$$$ 的元素插入。

可以注意到,在处理任意$$$i$$$后,序列$$$[a_1, a_2, \ldots, a_i]$$$的前缀是按非降序排序的,因此,该算法确实对任意序列进行了排序。

例如,对 $$$[4, 5, 3, 1, 3]$$$ 进行排序的过程如下:

- $$$i = 2$$$: $$$a_2 \ge a_1$$$,什么也不做;
- $$$i = 3$$$: $$$j = 1$$$, 从位置$$$3$$$插入到位置$$$1$$$: $$$[3, 4, 5, 1, 3]$$$;
- $$$i = 4$$$: $$$j = 1$$$, 从位置$$$4$$$插入到位置$$$1$$$: $$$[1, 3, 4, 5, 3]$$$;
- $$$i = 5$$$: $$$j = 3$$$,从位置 $$$5$$$ 插入到位置 $$$3$$$: $$$[1, 3, 3, 4, 5]$$$。

给定一个整数 $$$n$$$ 和一个 $$$m$$$ 整数对列表 $$$(x_i, y_i)$$$。我们对序列感兴趣,如果使用上述算法对它们进行排序,将执行精确的 $$$m$$$ 插入:首先从位置 $$$x_1$$$ 到位置 $$$y_1$$$,然后从位置 $$$x_2$$$ 到位置 $$$y_2$$$,...,最后,从位置 $$$x_m$$$ 到位置 $$$y_m$$$。

有多少个长度为 $$$n$$$ 且由 $$$1$$$ 和 $$$n$$$(含)之间的整数(不一定不同)组成的序列满足上述条件?打印此数字对 $$$998\,244\,353$$$ 取模。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$0 \le m < n$$$) - 序列的长度和插入的数量。

以下 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$2 \le x_1 < x_2 < \ldots < x_m \le n$$$; $$$1 \le y_i < x_i$$$)。这些行按时间顺序描述了插入的顺序。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。请注意,同类 $$$n$$$ 的总和没有限制。

输出

对于每个测试用例,打印长度为 $$$n$$$ 的序列数,该序列由从 $$$1$$$ 到 $$$n$$$ 的整数组成,以便使用所描述的算法对它们进行排序会产生给定的插入序列,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

3
3 0
3 2
2 1
3 1
5 3
3 1
4 1
5 3

输出 #1

10
1
21

注意

在第一个测试用例中,算法不执行插入 - 因此,初始序列已经按非降序排序。有$$$10$$$这样的序列:$$$[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 3], [2, 2, 2], [2, 2, 3], [2, 3, 3], [3, 3, 3]$$$。

在第二个测试用例中,唯一满足条件的序列是$$$[3, 2, 1]$$$。

在第三个测试用例中,$$$[4, 5, 3, 1, 3]$$$ 是所寻找的序列之一。