← 返回题目列表

Codeforces · 2124/F1

F1. 附加排列(简单版)

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

这是问题的简单版本。版本之间的差异在于,在此版本中,$$$n \leq 100$$$。只有解决了该问题的所有版本,您才能破解。

给你一个最初为空的数组$$$a$$$。您可以多次执行以下操作:

  • 选择一个整数 $$$s \ge 1$$$ 并将数组 $$$[1, 2, \ldots, s]$$$ 的循环移位附加到 $$$a$$$ 的末尾。形式上,选择整数 $$$s$$$ 和 $$$r$$$ 使得 $$$1 \le r \le s$$$,并附加数组

    $$[r, r+1, \ldots, s, 1, 2, \ldots, r-1]$$

    到 $$$a$$$ 的末尾。

您还会获得一个整数 $$$n$$$ 和 $$$m$$$ 限制,其形式为 $$$a_i \ne x$$$。也就是说,对于每个 $$$m$$$ 限制,最终数组中位置 $$$i$$$ 处的值不得等于 $$$x$$$。

您的任务是计算长度恰好为 $$$n$$$ 的不同数组的数量,这些数组可以使用允许的操作构造并满足所有给定的限制。如果两个数组在 $$$1$$$ 到 $$$n$$$ 之间的任何位置不同,则认为它们不同。

打印以 $$$998\,244\,353$$$ 为模的答案。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 100, 0 \leq m \leq \min(5000, n^2)$$$) - 表示数组 $$$a$$$ 的长度和限制数量。

接下来的 $$$m$$$ 行每行包含两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \leq i,x \leq n$$$),表明 $$$a_i\neq x$$$ 是最终数组的要求。保证不会多次给出限制。

保证所有测试用例的$$$n$$$总和不超过$$$100$$$,所有测试用例的$$$m$$$总和不超过$$$5000$$$。

输出

对于每个测试用例,输出以 $$$998\,244\,353$$$ 为模的数组数量。

示例

输入
复制

7
3 0
3 3
1 1
2 1
3 1
3 2
1 1
2 1
6 2
2 3
4 2
2 3
1 2
2 2
1 1
4 3
2 2
3 2
4 2
3 2
2 3
3 3

输出
复制

7
0
1
65
0
4
5

输入
复制

1
100 1
69 69

输出
复制

381055417

注意

在第一个测试用例中,总共可获得 $$$7$$$ 数组:$$$[1,2,3]、[2,3,1]、[3,1,2]、[1,1,2]、[1,2,1]、[2,1,1]、[1,1,1]$$$。

在第二个测试用例中,上述 $$$7$$$ 均无效,因为不允许任何元素为 $$$1$$$,并且所有数组都至少有一个 $$$1$$$。

在第三种情况下,仅计算$$$[2,3,1]$$$。