CF772D Varying Kibibits

给定 $n$ 个整数 $a_{1},a_{2},...,a_{n}$，将这个整数序列记为 $T$。 定义一个对非空整数序列 $L$ 作用的函数 $f(L)$。 函数 $f$ 的输出过程如下： - 首先，将 $L$ 中所有整数补齐前导零，使其长度等于 $L$ 中最大数字的位数。 - 然后构建一个字符串，第 $i$ 位字符等于所有补齐后数字的第 $i$ 位上的最小值。 - 最后将这个字符串作为十进制下的整数输出。 例如 $f(10,9)=0$，$f(123,321)=121$，$f(530,932,81)=30$。 定义函数 $$ G(x)=x\cdot\left((\sum_{S\subseteq T,S\neq \varnothing,f(S)=x}(\sum_{y\in S}y)^2)\bmod (10^9+7)\right) $$ 其中，$\subseteq$ 表示子序列。也就是说，$G(x)$ 是所有非空子序列 $S$ 满足 $f(S)=x$ 时，对 $(\sum_{y\in S}y)^2$ 求和后对 $10^9+7$ 取模，再乘以 $x$，注意最后一次乘法不取模。 你需要计算 $G(0),G(1),...,G(999999)$。为了减少输出体积，输出 $G(0)\oplus G(1)\oplus G(2)\oplus \cdots\oplus G(999999)$ 的值，这里 $\oplus$ 表示按位异或运算。

第一行包含一个整数 $n$（$1 \leq n \leq 1000000$），表示序列 $T$ 的长度。 第二行包含 $n$ 个用空格分隔的整数 $a_{1},a_{2},...,a_{n}$（$0 \leq a_{i} \leq 999999$），表示序列中的元素。

输出一个整数，即最终的答案。

对于第一个样例，唯一非零的 $G$ 值为 $G(121)=144611577$、$G(123)=58401999$、$G(321)=279403857$、$G(555)=170953875$。这些数的按位异或结果为 $292711924$。 例如，$G(123)=123\cdot((123^2+(123+555)^2)\bmod (10^9+7))=58401999$，因为所有满足 $f(S)=123$ 的子序列只有 $[123]$ 和 $[123,555]$。 第二个样例中，$G(999999)=999999\cdot(999999^2\bmod (10^9+7))$ 最后一个样例中，$G(1)=\sum_{i=1}^{10}\binom{10}{i}i^2=28160$，其中 ${10\choose i}$ 表示二项式系数。 由 ChatGPT 5 翻译