自动搬运

查看原文

来自洛谷，原作者为

	Silviasylvia 数声风笛离亭晚，君向潇湘我向秦。

搬运于2025-08-24 21:49:05，当前版本为作者最后更新于2022-08-03 15:35:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先有一种暴力方法，就是位数从高到低直接数位 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);