#P19001. 受限序列

    ID: 18337 传统题 2000ms 1024MiB 尝试: 57 已通过: 8 难度: 6 上传者: 标签>难度分类提高动态规划计数 DP0/1 背包线性 DP状态维度消除模拟与实现技巧预计算转移滚动数组CF2100

受限序列

受限序列

时间限制:2 秒 空间限制:1024 MiB

使用标准输入、标准输出。

题目描述

给定正整数 nn,考虑长度为 nn 的整数序列 a1,a2,…,ana_1,a_2,\ldots,a_n,要求:

$$a_1=0,\qquad a_{i+1}-a_i\in\{0,1\}\quad(1\le i<n).$$

记序列的前缀和为 sp=∑i=1pais_p=\sum_{i=1}^{p}a_i。

现给出 mm 条限制,每条限制由两个整数 (pj,vj)(p_j,v_j) 表示,要求 spj=vjs_{p_j}=v_j。求同时满足所有要求的序列数量,对 998244353998244353 取模。若不存在这样的序列,输出 00。

输入格式

第一行包含整数 TT,表示测试用例数。

对每个测试用例:

第一行包含两个整数 n,mn,m。

接下来 mm 行,每行包含两个整数 pj,vjp_j,v_j。保证 pjp_j 严格递增。

输出格式

对每个测试用例输出一行,包含一个整数,表示答案。

样例

输入

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

输出

1
1
2
2
2
0

样例第二个测试用例只有序列 (0,0,1)(0,0,1) 满足要求。第三个测试用例的合法序列为 (0,0,0)(0,0,0)、(0,0,1)(0,0,1)。

数据范围

所有测试用例均满足:

  • 1≤T≤100001\le T\le 10000;
  • 1≤n≤1001\le n\le100,0≤m≤n0\le m\le n;
  • 1≤p1<p2<⋯<pm≤n1\le p_1<p_2<\cdots<p_m\le n;
  • 0≤vj≤1090\le v_j\le10^9。

没有额外的所有测试用例 nn 之和上限。 当 m=0m=0 时,该测试用例不包含任何限制行。

本校训练分组

以下分组为本校本次训练设置,每组内所有测试文件均通过才获得该组分数。

分组 分值 额外条件
1 15 n≤12n\le12
2 n≤30n\le30
3 m≤1m\le1
4 m=nm=n
5 40 无额外条件

各组均遵守上述完整数据范围,测试用例数仍可能达到 1000010000。


题目原作:电子科技大学命题组,2026 ICPC 成都区域赛。中文整理及本校评分分组已作调整;题面遵循 CC BY-SA 4.0。

下发文件

大样例输入与输出