AT_xmascon25_e.Evaluation

给定整数 $M, N, A, B, C, D, E, F, G, H$。定义整数序列 $p_0, p_1, \ldots, p_{M-1}$ 与 $q_0, q_1, \ldots, q_{N-1}$，如下所示：

• $p_0 = A$，$p_i = (B p_{i-1} + C) \bmod D$（$1 \le i \le M-1$）。
• $q_0 = E$，$q_j = (F q_{j-1} + G) \bmod H$（$1 \le j \le N-1$）。

定义以 $x$ 为变量的多项式 $f(x) = \sum_{i=0}^{M-1} p_i x^i$。对于每个 $j = 0, 1, \ldots, N-1$，设 $r_j = f(q_j) \bmod 3^{19}$。

请计算并输出 $r_0, r_1, \ldots, r_{N-1}$ 的按位异或（XOR）。

其中，对于整数 $a$ 和正整数 $b$，$a \bmod b$ 表示 $a$ 除以 $b$ 的余数（结果在 $0$ 到 $b-1$ 之间）。

输入从标准输入中按以下格式提供。

$M$ $N$ $A$ $B$ $C$ $D$ $E$ $F$ $G$ $H$

输出 $r_0, r_1, \ldots, r_{N-1}$ 的按位异或所得的结果。

样例解释 1

$(p_0, p_1, p_2) = (1, 3, 4),\ (q_0, q_1, q_2, q_3) = (2, 0, 8, 6),\ (r_0, r_1, r_2, r_3) = (23, 1, 281, 163)$。

数据范围

• $1 \le M \le 10^7$。
• $1 \le N \le 10^7$。
• $0 \le A, B, C < D \le 10^9$。
• $0 \le E, F, G < H \le 10^9$。

由 ChatGPT 5 翻译