CF449D Jzzhu and Numbers 做题记录

给出一个长度为n的序列 $a_1,a_2...a_n$。求构造出一个序列 $i_1 < i_2 < ... < i_k(1\le{k}\le{n})$ 使得 $a_{i_1}\&a_{i_2}\&...\&a_{i_k}=0$。求方案数模 $10^9+7$。

也就是从$\{a_i\}$ 里面选出一个非空子集使这些数按位与起来为0。

首先记 $x$“包含”$y$ 当且仅当 $x\&y=y$，那么可以用 $dp_i$ 表示按位与和包含 $i$ 的最长子序列长度，有转移 $dp_{i-2^j}\to dp_{i-2^j}+dp_{i}$，其中 $i$ 包含 $2^j$。边界是 $dp_{a_i}=1$。

scanf("%d",&n);
for(int i=1;i<=n;i++)
{
	scanf("%d",&a[i]);
	dp[a[i]]++;
}
for(int j=0;j<=25;j++) // 注意转移顺序，要先枚举 j 再枚举 i，要不然会算重
{
	for(int i=1;i<=1000002;i++)
	{
		if((i>>j)&1)
		{
			dp[i^(1<<j)]=dp[i^(1<<j)]+dp[i];
		}
	}
}

考虑答案的求解，令 $pd_i$ 表示与和包含 $i$ 的子序列个数，显然有 $pd_i=2^{dp_i}-1$。试着用容斥求出答案，令 $g_i$ 表示所有满足 $j$ 的二进制中有 $i$ 个 $1$ 的 $pd_j$ 的和，答案即为 $g_0-g_1+g_2-g_3+g_4-g_5+\dots$

完整代码：

#include <iostream>
#include <cstdio>

using namespace std;

const int mod=1000000007;

int n,a[1000005];
int bse[1000005],dp[1000005],g[30];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		dp[a[i]]++;
	}
	for(int j=0;j<=25;j++) // 注意转移顺序，要先枚举 j 再枚举 i，要不然会算重
	{
		for(int i=1;i<=1000002;i++)
		{
			if((i>>j)&1)
			{
				dp[i^(1<<j)]=dp[i^(1<<j)]+dp[i];
			}
		}
	}
	bse[0]=1;
	for(int i=1;i<=n;i++)
	{
		bse[i]=2ll*bse[i-1]%mod;
	}
	for(int i=0;i<=1000002;i++)
	{
		int cnt=0;
		for(int j=0;j<=25;j++)
		{
			cnt+=(i>>j)&1;
		}
		g[cnt]=((long long)g[cnt]+bse[dp[i]]-1+mod)%mod; // 长度为 dp[i] 的序列里取子序列有 2^dp[i]-1 种方案 
	}
	int ans=g[0];
	for(int i=1;i<=25;i++)
	{
		if(i&1)
		{
			ans=(ans-g[i]+mod)%mod;
		}
		else
		{
			ans=(ans+g[i])%mod;
		}
	}
	printf("%d\n",ans);
	return 0;
}