前置知识：快速沃尔什变换（FWT）

考虑使用 FWT 的高维扩展，这里的按位取 \min 对应与运算。

将原序列 DWT，求出每个十进制数的超集和。那么现在要对每个位置的超集构成的集合的每个子集，求出它里面元素的和的平方，然后求和。

用数学语言表达，假设某个位置的超集构成的集合为 T，那么它的答案为

我们把平方拆掉：

考虑每个元素的贡献：

也就是说，我们需要 DWT 预处理每个元素的 0-2 次幂。这样求出来的答案也是超集和，所以要 IDWT 回去才是真正的答案。

实际上就是高维后缀和与差分。代码：

#include <cstdio>
const int MAXN=1100000;
const int P=1E9+7;
int a[MAXN], b[MAXN], c[MAXN];
int pow2[MAXN];
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i=1; i<=n; i++)
    {
        int s; scanf("%d", &s);
        a[s]++, b[s]+=s, c[s]=(c[s]+1ll*s*s)%P;
    }
    int t[]={1, 10, 100, 1000, 10000, 100000};
    for (int i=0; i<6; i++)
        for (int s=1E6-1; s>=0; s--)
            if (s/t[i]%10<9)
            {
                a[s]=(a[s]+a[s+t[i]])%P;
                b[s]=(b[s]+b[s+t[i]])%P;
                c[s]=(c[s]+c[s+t[i]])%P;
            }
    pow2[0]=1;
    for (int i=1; i<=n; i++) pow2[i]=2*pow2[i-1]%P;
    for (int s=0; s<1E6; s++)
        if (a[s]>=2) c[s]=pow2[a[s]-2]*(1ll*b[s]*b[s]%P+c[s])%P;
    for (int i=0; i<6; i++)
        for (int s=0; s<1E6; s++)
            if (s/t[i]%10<9) c[s]=(c[s]-c[s+t[i]]+P)%P;
    long long ans=0;
    for (int s=0; s<1E6; s++) ans^=1ll*s*c[s];
    printf("%lld\n", ans);
    return 0;
}