CF1707F Bugaboo

对于一个正整数数组 $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$。我们称一个数组 $c_1,c_2,\dots,c_n$（$0 \le c_i \le 2^w-1$）为 bugaboo，当且仅当存在一个数组 $a_1,a_2,\dots,a_n$，使得对 $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] \to [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] \to [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$（丢失位置可以任意取值）是 bugaboo。输出第 $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$ 行，每行包含两个整数 $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$ 次修改操作。 接下来的 $q$ 行，每行包含三个整数 $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$ 个位置变为丢失，否则表示将第 $f_i$ 个位置变为已知，且 $c_{f_i} = g_i$。$p_i$ 表示你需要输出第 $i$ 次修改的答案对 $p_i$ 取模的结果。

输出 $q$ 行，每行一个答案。

在第一个样例中，$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]$ 是 bugaboo。$[1,1,0]$ 可以通过对 $[1,0,1]$ 进行一次变换得到。所以答案是 $2 \bmod 555\,555\,555 = 2$。 由 ChatGPT 4.1 翻译