UOJ Logo Universal Online Judge

UOJ

附件下载 统计

跳蚤国王的密码本是一个长为 $n$,字符集为 $\{0, \dots, p-1\}$ 的字符串。跳蚤国王考虑了一种简单的哈希算法,取底数为 $b$,字符串 $\mathbf{s}=s_0s_1\dots s_{n-1}$ 的哈希值就是 $H(\mathbf{s}, b)=\sum_{i=0}^{n-1} s_i b^i \bmod p$。接着,跳蚤国王随机生成了一个字符串 $\mathbf{s}$,并选取了数 $q$,带入哈希函数验证了 $b=1,q,\dots,q^{n-1}$ 的这些情况。经过计算之后,跳蚤国王惊讶地发现仅对于 $k$ 个 $i$,$b=q^i$ 时的字符串哈希值不为 $0$。

这个消息被 Skip 蚤知道了,并且它已经窃取到了 $p, q, n$ 和这 $k$ 组 $(i, H(\mathbf{s}, q^i))$ 的值。此外,它还得知 $s_m$ 就是跳蚤国王的电脑登录密码。现在 Skip 蚤需要还原出 $s_m$ 的值。

这样,它就可以潜入 UOJ 服务器并把自己的 rating 改为 $8000$ ,并让跳蚤国王无法登陆电脑改回来了。

本题取 $p=998244353$,且保证 $1,q,\dots,q^{n-1}$ 在 $\bmod p$ 下是互不相同的,可以证明此时 $s_m$ 被唯一确定。

输入格式

第一行输入四个整数 $n, m, k, q$。分别表示字符串的长度,询问字符串位置,非零哈希值数量,以及所选的底数公比。

接下来 $k$ 行每行两个整数 $i, v$ 表示 $H(\mathbf{s}, q^i) = v$。

输出格式

输出一个数 $s_m$。

样例一

input

3 0 3 10
0 6
1 123
2 10203

output

3

explanation

不难验证 $\mathbf{s} = \texttt{321}$。因此 $s_0=3$。

样例二

input

2 0 2 998244352
0 132
1 666

output

399

样例三

input

2000 0 10 3
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

output

19212461

限制与约定

对于 $100\%$ 的数据,保证 $1\le n\le p-1, 0\le m\le n-1, 1\le k\le \min(n, 10^5), 1\le q\le p-1, 0\le i\le n-1, 1\le v\le p-1$,且输入的 $i$ 互不相同,$1,q,\dots,q^{n-1}$ 在 $\bmod p$ 下互不相同。

子任务编号 $n\le$ $k\le$ 特殊性质 分值
$1$ $2\times 10^3$ $5$
$2$ $10^6$ $1$ $10$
$3$ $10^7$ $5$
$4$ $p-1$ $15$
$5$ $10^6$ $10^5$ $10$
$6$ $10^7$ $20$
$7$ $p-1$ $q^n=1$ $10$
$8$ $2\times 10^3$ $15$
$9$ $10^5$ $10$

时间限制:$3\texttt{s}$

空间限制:$1\texttt{GB}$

下载

样例数据下载