配点 : 800 点
Library Checker 的多点评估 中尝试了惊人的加速。因此,我们准备了更容易区分执行时间的规模的测试。给定
問題文
整数 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} 的按位异或。
但是,表示小于整数 a 和一个正整数 从范围 b , 定义a \bmod b 在 a 该值应乘以 b 除以的余数0 以上 b 的数)
制約
- 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.
入力
输入是按以下格式从标准输入给出的。
M N A B C D E F G H
出力
r_0, r_1, \ldots, r_{N-1} 输出按位异或。
入力例 1
3 4 1 5 7 9 2 6 8 10
出力例 1
428
(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) 变为。
入力例 2
1000 2000 0 1 1 1000000000 0 1 1 1000000000
出力例 2
663657950