CF446E DZY Loves Bridges

DZY 拥有 $2^{m}$ 座靠近家园的小岛，这些小岛从 $1$ 到 $2^{m}$ 编号。他喜欢修建桥梁来连接这些岛屿。每跨过一座桥需要花费一天时间。 DZY 有一个特殊的修桥规则。对于任意一对不同的岛屿 $u,v$（$u\neq v$），如果 $2^{k}$ 能整除 $u \oplus v$，他就在它们之间修建了 $2^k$ 座不同的桥。 此外，DZY 还修建了一些桥梁将自己的家与各座小岛相连。具体来说，从家到第 $i$ 座小岛有 $a_i$ 座不同的桥。这些桥是单向的，也就是说他一旦离开了家就无法回去了。 DZY 决定去小岛观光。一开始他在家中。他选择并通过一座与家相连的桥，抵达某个小岛。之后，他将在小岛上度过 $t$ 天。每天，他可以选择留在原地休息，或通过桥梁去往其他岛屿。同一座桥可以多次穿越，也允许在同一座岛屿上停留多天。 设在第 $t$ 天结束时，DZY 站在第 $i$ 座岛屿。记 $ans[i]$ 为第 $t$ 天后到达第 $i$ 座岛屿的方案总数。请计算每个 $i$ 的 $ans[i]$ 对 $1051131$ 取模。

为了避免输入过大，数组 $a$ 按如下方式生成。你将获得数组的前 $s$ 个元素：$a_1, a_2, ..., a_s$。其余元素按如下公式递推：$a_i = (101 \cdot a_{i-s} + 10007)\bmod 1051131$ （$s < i \leq 2^m$）。 第一行包含三个整数 $m, t, s$，满足 $1 \leq m \leq 25$，$1 \leq t \leq 10^{18}$，$1 \leq s \leq \min(2^m, 10^5)$。 第二行给出 $s$ 个整数 $a_1, a_2, ..., a_s$，$1 \leq a_i \leq 10^6$。

为了避免输出过大，你只需输出所有 $ans[i]$ 对 $1051131$ 取模后的异或和，即 $(ans[1]\bmod 1051131)\operatorname{xor}(ans[2]\bmod 1051131)\operatorname{xor} \ldots \operatorname{xor}(ans[2^m]\bmod 1051131)$。

在第一个样例中，$ans = [6, 7, 6, 6]$。 如果他想在一天后站在岛屿 1，有 6 种不同方式： 1. 家 → 1 —(停留)—> 1 2. 家 → 2 → 1 3. 家 → 3 → 1 4. 家 → 3 → 1（注意 1 和 3 之间有两座桥） 5. 家 → 4 → 1 6. 家 → 4 → 1（注意家到 4 有两座桥） 在第二个样例中，$(a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8) = (389094, 705719, 547193, 653800, 947499, 17024, 416654, 861849)$，$ans = [235771, 712729, 433182, 745954, 139255, 935785, 620229, 644335]$。 由 ChatGPT 5 翻译