← 返回题目列表

Codeforces · 772/D

D. 变化千位

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

给定 n 个整数 a1, a2, ..., an。将此整数列表表示为 T。

设 f(L) 是一个接受非空整数列表 L 的函数。

该函数将输出另一个整数,如下所示:

- 首先,L 中的所有整数都用前导零填充,因此它们的长度都与 L 中的最大长度数相同。
- 我们将构造一个字符串,其中第 i 个字符是填充输入数字中第 i 个字符的最小值。
- 输出是表示以 10 为基数解释的字符串的数字。

例如 f(10, 9) = 0、f(123, 321) = 121、f(530, 932, 81) = 30。

定义函数

$$$$

换句话说,G(x) 是 T 的非空子序列的元素和的平方和,当将其插入 f 模 1 000 000 007,然后乘以 x 时,其结果为 x。最后一个乘法没有被修改。

您想要计算 G(0), G(1), ..., G(999 999)。要减小输出大小,请打印值 $$G(0) \oplus G(1) \oplus G(2) \oplus \ldots \oplus G(999\ 999)$$,其中 $$\bigcirc$$ 表示按位 XOR 运算符。

输入

第一行包含整数 n (1 ≤ n ≤ 1 000 000) — 列表 T 的大小。

下一行包含 n 个空格分隔的整数,a1, a2, ..., an (0 ≤ ai ≤ 999 999) - 列表的元素。

输出

输出一个整数,即问题的答案。

示例

输入 #1

3
123 321 555

输出 #1

292711924

输入 #2

1
999999

输出 #2

997992010006992

输入 #3

10
1 1 1 1 1 1 1 1 1 1

输出 #3

28160

注意

对于第一个样本,G 的非零值为 G(121) = 144 611 577、G(123) = 58 401 999、G(321) = 279 403 857、G(555) = 170 953 875。这些数字的按位异或等于 292 711924。

例如, $$G(123) = 123 \cdot \left( ( ( 1 2 3 ) ^ { 2 } + ( 1 2 3 + 5 5 5 ) ^ { 2 } ) \right) \bmod 100000007 = 58401999$$,因为子序列 [123] 和[123, 555] 插入 f 时计算结果为 123。

对于第二个样本,我们有 $$G(999\ 999) = 999\ 999 \cdot (999\ 999^2 \bmod 1\ 000\ 000\ 007)$$

对于最后一个样本,我们有 $$G(1) = \sum_{i=1}^{10} {10 \choose i} i^2 = 28160$$,其中 $${ \binom { 10 } { i } }$$ 是二项式系数。