#P19001. 受限序列
受限序列
受限序列
时间限制:2 秒 空间限制:1024 MiB
使用标准输入、标准输出。
题目描述
给定正整数 ,考虑长度为 的整数序列 ,要求:
$$a_1=0,\qquad a_{i+1}-a_i\in\{0,1\}\quad(1\le i<n).$$记序列的前缀和为 。
现给出 条限制,每条限制由两个整数 表示,要求 。求同时满足所有要求的序列数量,对 取模。若不存在这样的序列,输出 。
输入格式
第一行包含整数 ,表示测试用例数。
对每个测试用例:
第一行包含两个整数 。
接下来 行,每行包含两个整数 。保证 严格递增。
输出格式
对每个测试用例输出一行,包含一个整数,表示答案。
样例
输入
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
样例第二个测试用例只有序列 满足要求。第三个测试用例的合法序列为 、。
数据范围
所有测试用例均满足:
- ;
- ,;
- ;
- 。
没有额外的所有测试用例 之和上限。 当 时,该测试用例不包含任何限制行。
本校训练分组
以下分组为本校本次训练设置,每组内所有测试文件均通过才获得该组分数。
| 分组 | 分值 | 额外条件 |
|---|---|---|
| 1 | 15 | |
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | 40 | 无额外条件 |
各组均遵守上述完整数据范围,测试用例数仍可能达到 。
题目原作:电子科技大学命题组,2026 ICPC 成都区域赛。中文整理及本校评分分组已作调整;题面遵循 CC BY-SA 4.0。
下发文件
相关
在下列比赛中: