你取个模会死，吗，，，

· · 题解

首先有一种暴力方法，就是位数从高到低直接数位 dp，记录当前每一个数的上限是否取满了，但这样复杂度显然是爆炸的。我们考虑有没有什么性质可以优化这个过程。

异或有一个很优秀的性质；a\oplus b \oplus c=0，那么 a\oplus b=c，所以我们发现，只要确定了前 n-1 个数，第 n 个数也就确定了，只要考虑是否在范围内即可。

然后就容易多了，首先不难发现如果 a_n=2^{32}-1 的话，那么答案就为 \prod\limits_{i=1}^n(a_i+1)-1，这还是在引导你从高位到低位考虑：如果你在一个高位没取满，在低位就可以任意取。

于是顺着这个思路从高位考虑，当前在第 j 位（最低位算 0），设有 k 个数在当前位是 1，那么如果你有任意一个当前位为 1 的数没取 1，那么你可以立即用上面的式子算出答案，否则就一定是全部取了 1，那就把这位去掉，成为了一个 j-1 位的子问题。

假如有 t 个当前位是 1，但是没取 1 的，那么这个集合里面有一个需要用在最后被确定的那个，除了这个之外的都可以任选。这个过程可以 O(n) dp 解决。

具体的，设 dp_{i,0/1} 表示考虑到前 i 个，这一位目前的异或值是 0/1 的答案总和，转移显然。当前位的答案就为 dp_{n,0}。

一些细节：

  1. 如果当前位为 1 的个数是偶数（第 0 位除外），那么最终的 dp 值就需要减去 \prod\limits_{i=1}^n((a_i\mod 2^j)+1)，因为这包含了全部选的方案，但是如果全部选的话实际上应该考虑在 j-1 的子问题中，所以不能算。
  2. 你在算有 1 的最高位的贡献的时候，会把全部是 0 的方案算进去，因此最终 ans 要减 1。
  3. 如果当前位有奇数个 1，那么统计完就直接退出循环（显然）。
  4. 答案会爆 ll，建议开 int128。

复杂度 O(n\log m)。

核心代码：

rdn;
upn rd(a[i]);
int ans=0;
pu(j,31,0)
{
    int st=0;
    up(i,1,n)
    {
        if(a[i]&(1<<j))++st;
    }
    dp[0][0]=1;
    int ww=1;
    up(i,1,n)
    {
        if(a[i]&(1<<j))
        {
            dp[i][0]=dp[i-1][1]*(a[i]%(1<<j)+1);
            dp[i][1]=dp[i-1][0]*(a[i]%(1<<j)+1);
            dp[i][0]+=dp[i-1][0]*(1<<j);
            dp[i][1]+=dp[i-1][1]*(1<<j);
        }
        else
        {
            dp[i][0]=dp[i-1][0]*(a[i]%(1<<j)+1);
            dp[i][1]=dp[i-1][1]*(a[i]%(1<<j)+1);
        }
        ww*=(a[i]%(1<<j)+1);
    }
    int vl=0;
    vl=dp[n][0];
    if(st%2==0)vl-=ww;
    if(st%2==0&&j==0)vl+=ww;
    vl/=(1<<j);
    ns+=vl;
    if(st&1)
    {
        break;
    }
}
print(ans-1);