滚动哈希

时间限制：2s
空间限制：1024MB

题目描述

给定非负整数 $P,B$，其中 $P$ 是质数且 $1\le B<P$。对非负整数序列 $X=(x_1,x_2,\ldots,x_n)$，定义

$$\operatorname{hash}(X)=\left(\sum_{i=1}^n x_iB^{n-i}\right)\bmod P.$$

另给出 $M$ 个互不相同的区间 $(L_i,R_i)$。判断是否存在长度为 $N$ 的非负整数序列 $A$，使每个区间子序列 $(A_{L_i},A_{L_i+1},\ldots,A_{R_i})$ 的哈希值都不为 $0$。

输入格式

第一行四个整数 $P,B,N,M$，接下来 $M$ 行每行两个整数 $L_i,R_i$。

输出格式

若存在满足条件的序列，输出 Yes；否则输出 No。

样例输入 1

3 2 3 3
1 1
1 2
2 3

样例输出 1

Yes

样例输入 2

2 1 3 3
1 1
2 3
1 3

样例输出 2

No

数据范围

• $2\le P\le10^9$，且 $P$ 为质数。
• $1\le B<P$，$1\le N\le16$。
• $1\le M\le\frac{N(N+1)}2$。
• $1\le L_i\le R_i\le N$，所有区间互不相同。

把每个区间 $(L_i,R_i)$ 视为连接顶点 $L_i$ 与 $R_i+1$ 的边，得到一个 $N+1$ 个顶点的无向图。

子任务编号	分值	特殊限制
1	8	$N\le7$
2	12	$P=2$
3	15	上述无向图的最大度数不超过 $2$
4		上述无向图是弦图
5	20	$N\le12$
6	30	无特殊限制