← 返回题目列表

Codeforces · 1707/F

F. 布加布

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

正整数数组 $$$a_1,a_2,\dots,a_n$$$ 的转换是通过将 $$$a$$$ 替换为 $$$b_1,b_2,\dots,b_n$$$ 给出的数组 $$$b_i=a_i\oplus a_{(i\bmod n)+1}$$$ 来定义的,其中$$$\oplus$$$ 表示按位异或运算。

给定整数 $$$n$$$、$$$t$$$ 和 $$$w$$$。当且仅当存在数组 $$$a_1,a_2,\dots,a_n$$$ 时,我们认为数组 $$$c_1,c_2,\dots,c_n$$$ ($$$0 \le c_i \le 2^w-1$$$) 是 bugaboo,这样在将 $$$a$$$ 转换 $$$t$$$ 次后,$$$a$$$ 变为$$$c$$$。

例如,当 $$$n=6$$$、$$$t=2$$$、$$$w=2$$$ 时,则数组 $$$[3,2,1,0,2,2]$$$ 是 bugaboo,因为它可以通过将数组 $$$[2,3,1,1,0,1]$$$ 转换 $$$2$$$ 次来给出:

$$$$$$ [2,3,1,1,0,1]\到[2\oplus 3,3\oplus 1,1\oplus 1,1\oplus 0,0\oplus 1,1\oplus 2]=[1,2,0,1,1,3]; \\ [1,2,0,1,1,3]\到[1\oplus 2,2\oplus 0,0\oplus 1,1\oplus 1,1\oplus 3,3\oplus 1]=[3,2,1,0,2,2]。 $$$$$$

数组 $$$[4,4,4,4,0,0]$$$ 不是 bugaboo,因为 $$$4 > 2^2 - 1$$$。数组 $$$[2,3,3,3,3,3]$$$ 也不是 bugaboo,因为它不能通过将一个数组转换 $$$2$$$ 次来给出。

给定一个数组 $$$c$$$,其中丢失了一些位置(一开始只知道 $$$m$$$ 位置,其余位置都丢失了)。还有 $$$q$$$ 修改,其中每个修改都改变 $$$c$$$ 的位置。修改可能会改变位置是否丢失或已知,并且可能会重新定义已经给定的位置。

您需要计算每次修改后有多少个可能的数组 $$$c$$$ (丢失位置上有任意元素)是 bugabos。输出第 $$$i$$$ 答案对 $$$p_i$$$ 取模($$$p_i$$$ 是由 $$$q$$$ 元素组成的给定数组)。

输入

第一行包含四个整数 $$$n$$$、$$$m$$$、$$$t$$$ 和 $$$w$$$ ($$$2\le n\le 10^7$$$, $$$0\le m\le \min(n, 10^5)$$$, $$$1\le t\le 10^9$$$, $$$1\le w\le 30$$$)。

以下 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$d_i$$$ 和 $$$e_i$$$ ($$$1\le d_i\le n$$$, $$$0\le e_i< 2^w$$$)。这意味着数组 $$$c$$$ 的位置 $$$d_i$$$ 已给出,且 $$$c_{d_i}=e_i$$$。保证$$$1\le d_1<d_2<\ldots<d_m\le n$$$。

下一行仅包含一个数字 $$$q$$$ ($$$1\le q\le 10^5$$$) — 修改次数。

以下 $$$q$$$ 行中的第 $$$i$$$ 行包含三个整数 $$$f_i$$$, $$$g_i$$$, $$$p_i$$$ ($$$1\le f_i\le n$$$, $$$-1\le g_i< 2^w$$$, $$$11\le p_i\le 10^9+7$$$)。值$$$g_i=-1$$$表示将数组$$$c$$$的位置$$$f_i$$$更改为丢失位置,否则表示将数组$$$c$$$的位置$$$f_i$$$更改为已知位置,且$$$c_{f_i}=g_i$$$。值 $$$p_i$$$ 表示您需要输出第 $$$i$$$ 模 $$$p_i$$$ 的答案。

输出

输出包含 $$$q$$$ 行,表示您的答案。

示例

输入 #1

3 2 1 1
1 1
3 1
4
2 0 123456789
2 1 111111111
1 -1 987654321
3 -1 555555555

输出 #1

1
0
1
2

输入 #2

24 8 5 4
4 4
6 12
8 12
15 11
16 7
20 2
21 9
22 12
13
2 13 11
3 15 12
5 7 13
9 3 14
10 5 15
11 15 16
13 14 17
14 1 18
18 9 19
19 6 20
23 10 21
24 8 22
21 13 23

输出 #2

1
4
9
2
1
0
1
10
11
16
16
0
16

注意

在第一个示例中,$$$n=3$$$、$$$t=1$$$ 和 $$$w=1$$$。令$$$?$$$ 表示$$$c$$$ 的损失头寸。

在第一个查询中,$$$c=[1,0,1]$$$。唯一可能的数组 $$$[1,0,1]$$$ 是 bugaboo,因为它可以通过转换 $$$[0,1,1]$$$ 一次来给出。所以答案是$$$1\bmod 123\,456\,789 = 1$$$。

在第二个查询中,$$$c=[1,1,1]$$$。唯一可能的数组 $$$[1,1,1]$$$ 不是 bugaboo。所以答案是$$$0\bmod 111\,111\,111 = 0$$$。

在第三个查询中,$$$c=[?,1,1]$$$。有两个可能的数组 $$$[1,1,1]$$$ 和 $$$[0,1,1]$$$。只有 $$$[0,1,1]$$$ 是 bugaboo,因为它可以通过转换 $$$[1,1,0]$$$ 一次来给出。所以答案是$$$1\bmod 987\,654\,321=1$$$。

在第四个查询中,$$$c=[?,1,?]$$$。有四种可能的数组。 $$$[0,1,1]$$$ 和 $$$[1,1,0]$$$ 是 bugaboos。 $$$[1,1,0]$$$ 可以通过执行 $$$[1,0,1]$$$ 一次来给出。所以答案是$$$2\bmod 555\,555\,555=2$$$。