304016: CF772D. Varying Kibibits
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Varying Kibibits
题意翻译
对于一个有$n$ 个元素的序列$a_1,a_2...a_n$ ,我们姑且把它称之为$T$ 然后对于一个非空序列$L$ ,我们定义函数$f(L)$ : 将$L$ 中的元素十进制下的高位用0补全,取每一位的最小值组成一个新数,作为函数的值。 定义函数$G(x)$ $$G(x)=x\left(((\sum_{S \subseteq T,S \neq \emptyset,f(S)=x} (\sum_{y \in S}y)^2) \bmod 1000000007\right)$$ 求$G(0) xor G(1) xor ... xor G(999999)$ 感谢@litble 提供的翻译题目描述
You are given $ n $ integers $ a_{1},a_{2},...,a_{n} $ . Denote this list of integers as $ T $ . Let $ f(L) $ be a function that takes in a non-empty list of integers $ L $ . The function will output another integer as follows: - First, all integers in $ L $ are padded with leading zeros so they are all the same length as the maximum length number in $ L $ . - We will construct a string where the $ i $ -th character is the minimum of the $ i $ -th character in padded input numbers. - The output is the number representing the string interpreted in base 10. For example $ f(10,9)=0 $ , $ f(123,321)=121 $ , $ f(530,932,81)=30 $ . Define the function ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF772D/d730bfc2d6a92400175f0319f4f66324ea578631.png) Here, ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF772D/cbe1963e07d9486bdfb07e1dbd14017f5caa5e0f.png) denotes a subsequence.In other words, $ G(x) $ is the sum of squares of sum of elements of nonempty subsequences of $ T $ that evaluate to $ x $ when plugged into $ f $ modulo $ 1000000007 $ , then multiplied by $ x $ . The last multiplication is not modded. You would like to compute $ G(0),G(1),...,G(999999) $ . To reduce the output size, print the value ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF772D/8f5e81fbdf6da04693b872f68826db1077fb8afc.png), where ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF772D/4298d47c0191af3c0a3103f431751061bc7e2362.png) denotes the bitwise XOR operator.输入输出格式
输入格式
The first line contains the integer $ n $ ( $ 1<=n<=1000000 $ ) — the size of list $ T $ . The next line contains $ n $ space-separated integers, $ a_{1},a_{2},...,a_{n} $ ( $ 0<=a_{i}<=999999 $ ) — the elements of the list.
输出格式
Output a single integer, the answer to the problem.
输入输出样例
输入样例 #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