分数: 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