题目背景
译自 COCI 2024/2025 #5 T4。2s,0.5G。满分为 120。
题目描述
考虑一个长度为 n 的整数序列 a1,…,an,初始时 ai∈{−1,0}。
你可以按照如下的步骤操作任意多次(包括零次):
- 令这是第 x 次操作。首先选择 i 满足 1≤i≤n,且 ai=0。(如果不存在,则无法继续操作)
- 从如下的操作中二选一:
- 令 ai←−1,然后终止本次操作。
- 令 ai←x。若 i≥2 且 ai−1=0,令 i←i−1,然后重新开始二选一(注意,若下一次二选一中选择令 ai−1←x,则有 ai−1=ai)。
操作完后会得到若干个结果序列 a。
我们称两个序列 a,b 等价,当且仅当,能够重标号 a 序列中 >0 的元素,使得重标号后这两个序列相等。
例如,[1,1,−1,5,1,0] 和 [2,2,−1,6,2,0] 等价。
更为精确地说,如果能构造一个双射 f:{−1,0,…}→{−1,0,…},满足:
- f(−1)=−1,f(0)=0;
- 对于 i>0,f(i)>0;
- [f(a1),f(a2),…,f(an)]=[b1,b2,…,bn]。
那我们就说,a 和 b 等价。
一开始 ai=0。
接着有 q 个操作,每个操作给定 l,r,将 al,al+1,…,ar 中的 0 同时替换成 −1,−1 同时替换成 0。
每次操作后,求出以当前的 a 序列为起始序列,操作得到的互不等价的结果序列的数量模 (109+7) 后的结果。
输入格式
第一行,正整数 n,q。
接下来 q 行,每行两个正整数 l,r,描述一次操作。
输出格式
输出 q 行,第 i 行一个非负整数,表示第 i 次操作得到的互不等价的序列数量模 (109+7) 后的结果。
1 2
1 1
1 1
1
3
3 2
2 2
1 3
9
3
57 2
13 39
6 42
130653412
804077942
提示
样例解释
样例 1 解释:
第一次操作后,a=[−1]。无法操作。互不等价的序列只有 [−1]。
第二次操作后,a=[0]。互不等价的序列有 [0],[1],[−1]。
数据范围
对于 100% 的数据,保证:
- 1≤n≤1018;
- 1≤q≤105;
- 1≤l≤r≤n。
子任务编号 |
n≤ |
特殊性质 |
得分 |
1 |
2×103 |
A |
20 |
2 |
106 |
|
55 |
3 |
1018 |
45 |
特殊性质 A:q≤2×103。