← 返回题目列表

AtCoder · arc171_d

D. 滚动哈希

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

分数: 600 点

问题陈述

给你非负整数 P 和 B。在这里, P 是素数,并且 1 \leq B \leq P-1.
对于非负整数序列 X=(x_1,x_2,\dots,x_n),哈希值 \mathrm{hash}(X) 定义如下。

\displaystyle \mathrm{hash}(X) = \left(\sum_{i=1}^n x_i B^{n-i}\right) \bmod P

你被给予 M 整数对 (L_1, R_1), (L_2, R_2), \dots, (L_M, R_M).
是否存在非负整数序列 A=(A_1, A_2, \dots, A_N) 长度 N 满足以下条件?

  • 对于所有人 i (1 \leq i \leq M),以下条件成立:
    • 让 s 是序列 (A_{L_i}, A_{L_i + 1}, \dots, A_{R_i}) 通过采取 L_i-第 R_i第一个元素 A。然后, \mathrm{hash}(s) \neq 0.

约束

  • 2 \leq P \leq 10^9
  • P 是质数。
  • 1 \leq B \leq P - 1
  • 1 \leq N \leq 16
  • 1 \leq M \leq \frac{N(N+1)}{2}
  • 1 \leq L_i \leq R_i \leq N
  • (L_i, R_i) \neq (L_j, R_j) if i \neq j.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

P B N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

输出

如果存在满足问题陈述中的条件的序列,则打印 Yes;否则,打印 No.


示例输入 1

3 2 3 3
1 1
1 2
2 3

示例输出 1

Yes

序列 A = (2, 0, 4) 满足条件,因为 \mathrm{hash}((A_1)) = 2, \mathrm{hash}((A_1, A_2)) = 1, \mathrm{hash}((A_2, A_3)) = 1.


示例输入 2

2 1 3 3
1 1
2 3
1 3

示例输出 2

No

没有序列满足条件。


示例输入 3

998244353 986061415 6 11
1 5
2 2
2 5
2 6
3 4
3 5
3 6
4 4
4 5
4 6
5 6

示例输出 3

Yes