← 返回题目列表

AtCoder · xmascon25_e

E. 评价

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

配点 : 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