Problem

Codechef

Solution

我们可以按位进行考虑，如果一个 \(m_i\) 在某一位上为1，但 \(x_i\) 却取了0，那么我们就称它脱离了限制，更低位可以随便乱填。也就是说，只要高位异或的方案合法，这些更低位，无论其他数怎么填，它都可以使得最终结果合法。

那么这就变成了一个比较方便考虑的计数问题了。可以枚举第一个脱离控制的最高位，然后由于可能有多个数脱离控制，我们就选择最后一个脱离控制的数来进行计数。注意如果这一位没有脱离限制，说明所有这一位有1的都填了1，而如果这种异或方案异或出来的0,1方案与k不相同，那么就是不合法的，及时break掉。

时间复杂度 \(O(n\log v)\)

Code

#include <cstring>

#include <cstdio>

using namespace std;

typedef long long ll;

const int maxn=100010,mod=1e9+9;

template <typename Tp> inline int getmin(Tp &x,Tp y){return y<x?x=y,1:0;}

template <typename Tp> inline int getmax(Tp &x,Tp y){return y>x?x=y,1:0;}

template <typename Tp> inline void read(Tp &x)

{

    x=0;int f=0;char ch=getchar();

    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

    if(ch=='-') f=1,ch=getchar();

    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();

    if(f) x=-x;

}

int z,n,k,ans,a[maxn],lim[32],cnt[32][maxn],f[maxn][2],g[maxn];

int pls(int x,int y){return x+y>=mod?x+y-mod:x+y;}

int solve(int x)

{

	int res=0;ll tmp,sum;

	memset(f,0,sizeof(f));

	memset(g,0,sizeof(g));

	f[0][0]=1;g[n+1]=1;

	for(int i=1;i<=n;i++)

	  for(int j=0;j<2;j++)

	  {

	  	if(a[i]>>x&1)

	  	{

	  		tmp=lim[x]-(1<<x)+1;

	  		f[i][j]=(f[i][j]+f[i-1][j]*tmp)%mod;

	  		tmp=(a[i]&lim[x])-(1<<x)+1;

	  		f[i][j]=(f[i][j]+f[i-1][j^1]*tmp)%mod;

	  	}

	  	else

	  	{

	  		tmp=(a[i]&lim[x])+1;

	  		f[i][j]=(f[i][j]+f[i-1][j]*tmp)%mod;

	  	}

	  }

	for(int i=n;i;i--)

	{

		if(a[i]>>x&1) g[i]=(ll)g[i+1]*((a[i]&lim[x])-(1<<x)+1)%mod;

		else g[i]=(ll)g[i+1]*((a[i]&lim[x])+1)%mod;

	}

	for(int i=1;i<=n;i++)

	  if(a[i]>>x&1)

		res=(res+(ll)f[i-1][(k>>x&1)^(cnt[x][i+1]&1)]*g[i+1])%mod;

	return res;

}

int main()

{

	read(z);

	lim[0]=1;

	for(int i=1;i<=30;i++) lim[i]=lim[i-1]<<1|1;

	while(z--)

	{

		read(n);ans=k=0;

		for(int i=1;i<=n;i++){read(a[i]);k^=a[i];}

		for(int j=30;~j;j--) cnt[j][n+1]=0;

		for(int i=n;i;i--)

		  for(int j=30;~j;j--)

			cnt[j][i]=cnt[j][i+1]+(a[i]>>j&1);

		for(int i=30;~i;i--)

		{

			ans=pls(ans,solve(i));

			if((cnt[i][1]&1)!=(k>>i&1)) break;

			ans=pls(ans,(i==0));

		}

		printf("%d\n",ans);

	}

	return 0;

}