#P17718. [2026年福建省队集训]于一
[2026年福建省队集训]于一
题目描述
有一条长度为 的街。令一个点的坐标范围为 ,且坐标一定是整数。
街上有 个灯笼,第 个灯笼在坐标 ,可设定的亮度范围在 ,任何一个灯笼的亮度一定为整数。
定义坐标在 ,亮度为 的灯笼能照亮坐标在 的点当且仅当 。
于一有 个关键点需要被照亮,其中第 个关键点的坐标为 。
因此于一可以给每个灯笼设定其亮度,并且他希望设定完亮度后每个关键点都能被至少一个灯笼照亮。
于一有若干个想法。对于第 次询问,他想知道如果他在坐标 新增了一个可设定的亮度范围在 的灯笼,那么有多少种不同的给每个灯笼设定亮度的方案满足——任意一个关键点都能至少被一个灯笼照亮。询问之间是独立的。且不存在两个灯笼(包括新增的灯笼)坐标相同,不存在两个关键点坐标相同。
由于答案可能很大,你只需要告诉于一满足要求的方案数,对 998244653 取模后的值。
两种设定亮度的方案不同,当且仅当存在一个灯笼在两种方式下被设定的亮度不同。
输入格式
第一行包含三个整数 。
接下来 行,每行包含两个整数 ,分别表示第 个灯笼的坐标和可设定的亮度上限。
接下来一行包含 个整数 ,表示关键点的坐标。
接下来一行包含一个整数 ,表示询问次数。
接下来 行,每行包含两个整数 ,分别表示新增的灯笼的坐标和可设定的亮度上限。
输出格式
输出 行,每行一个整数表示答案对 998244653 取模后的值。
样例输入
6 3 3
1 1
3 1
5 2
2 3 6
3
1 0
4 1
2 1
样例输出
8
24
8
样例解释
对于第一次询问,共有 8 种合法的方案。
新增的灯的亮度只能为 0,所有合法的方案如下:
- 设定第一个灯笼亮度为 0,第二个灯笼亮度为 0,第三个灯笼亮度为 1。
- 设定第一个灯笼亮度为 0,第二个灯笼亮度为 0,第三个灯笼亮度为 2。
- (下略)
数据范围
对于 的数据满足,,,,,。
保证 。
保证 。
保证 。
各测试点的具体限制见下表:
| 测试点 | 限制 |
|---|---|
| 1~2 | |
| 3~4 | |
| 5~6 | |
| 7~9 | |
| 10~11 | |
| 12~13 | $L \le 10^7, n \le 2\times 10^5, m \le 16, q \le 2\times 10^5$ |
| 14~16 | $L \le 10^7, n \le 3\times 10^5, m \le 30, q \le 2\times 10^5$ |
| 17~18 | $L \le 10^8, n \le 5\times 10^5, m \le 500, q \le 5\times 10^5$,满足特殊性质 A |
| 19~22 | $L \le 10^8, n \le 5\times 10^4, m \le 100, q \le 5\times 10^4$ |
| 23~25 | $L \le 10^8, n \le 5\times 10^5, m \le 500, q \le 5\times 10^5$ |
特殊性质 A:所有询问中的新增灯笼的坐标 都相同。