题目链接：http://acm.uestc.edu.cn/#/problem/show/1294
天行健，君子以自强不息。地势坤，廖爷以厚德载物
一日在喵哈哈村，天行廖和沈宝宝正在玩一个游戏。
天行廖分别在N
个纸片上写上一个数字，并放到一个盒子中。
现在沈宝宝要从盒子中抓出任意张纸片。
如果沈宝宝抓出的纸片上的数字Ai1
,Ai2,….Aik满足Ai1 & Ai2 & ….Aik=0 ，那么天行廖赢得这次游戏的胜利，否则沈宝宝赢。
Input
第一行输入1
个整数N。(1≤N≤106
)
第二行输入N
个整数A1，A2….AN。(1≤Ai≤106
)
Output
输出获胜的方案数量。因为结果可能很大，输出答案对109+7
取模的结果即可。
Sample input and output
Sample Input Sample Output
3
2 3 3
0
4
0 1 2 3
10
6
5 2 0 5 2 1
53
2
0 0
3
Hint
对于第4
组样例，三组合法的解是(A1),(A2),(A1，A2)
解法：
题解我是看的卿学姐的qrz，在电大的微信号里看到过这道题，一直不清楚怎么解，今天终于会了。引用卿学姐的解题报告：
首先，我们再看一遍题意：对于一个长度为n的数列a1,a2…an，挑出任意个数，使得这些数的且运算结果为0。
首先暴力2^n枚举是肯定不行的。考虑不那么暴力的DP做法，令dp[i][j]表示从前i个数选结果为j的方案有多少种，转移方程为dp[i][j] = sigma(dp[i - 1][k]) (k & a[i] = j)，复杂度为n^3，显然也不行…
于是我们考虑是否能用容斥原理做。1e6的二进制表达式有20位，总方案数为2^n，然后我们减去结果第一位为1的方案数，第二位为2的方案数…第二十位为1的方案数，即某一位为1的方案数。然后根据容斥原理，我们再加上结果某两位为1的方案数，减去结果某三位为1的方案数…，加上全为1的方案数。假设F(i)为结果为i的方案数量(令F(0) = 2 ^ n)，g(i)为i二进制下1的个数，则ans = sigma(F(i)*(-1)^(g(i)))。
那么现在问题即如何计算F(i)。若要使得k个数b1,b2…,bk的且运算为i，那么对于所有i为1的位，任意bj在该位置上也都为1，即bj & i = i。如果我们能算出满足aj & i = i的数的个数cnt(i)，就能得到F(i) = 2 ^ cnt(i)，于是问题转换为如何快速计算cnt(i)。
我们令cnt[k][i]表示只有前k位与i不同且满足aj & i = i的数的个数，边界cnt[0][i]表示正好为i的数的个数。现在分两种情况讨论cnt[k][i]的递推式:
1、i的第k位是1，那么cnt[k][i] = cnt[k - 1][i]，因为若第k位不同,则与i作且运算是第k位为0，所以相当于只有前k-1位不同。
2、i的第k位是0，则是第k位0或1没有影响,对比第一种情况需要加上前k-1位不同且第k位为1的数的个数。显然这个方案数等于dp[k - 1][i + 2^k]，则得到递推式cnt[k][i] = cnt[k - 1][i] + cnt[k - 1][i + 2 ^ k]。
因为位数K最大为log(1e6)约等于20,于是我们就能在O（NK）（K=20）的复杂度计算出cnt(i)，并在O（N）的时间内完成容斥的计算，总时间复杂度为O（NK）。至此，我们解完了这题。
然后代码的话就相对很简单了，容斥加DP的好题，大概可以想到要拆成位DP，但是容斥没想到，qrz。
//CDOJ 1294
//dp + 容斥
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1<<20;
const long long mod = 1e9+7;
long long dp[21][maxn];
///dp[i][x]表示,二进制下只有前i位可能与x不同的数与x进行and运算仍然为x的数的个数
long long g[maxn];
bool s[maxn];
int main()
{
int n;
scanf("%d", &n);
g[0] = 1;
for(int i = 1; i <= n; i++) g[i] = (g[i-1]<<1LL)%mod;
for(int i = 1; i <= n; i++){
int x;
scanf("%d", &x);
dp[0][x]++;
}
for(int i = 1; i <= 20; i++){
for(int j = 0; j < maxn; j++){
if((j&(1<<(i-1))) == 0){
dp[i][j] = dp[i-1][j] + dp[i-1][j|(1<<(i-1))];
}
else{
dp[i][j] = dp[i-1][j];
s[j] ^= 1;
}
}
}
long long ans = 0;
for(int i = 0; i < maxn; i++){
ans = (ans + (s[i] ? (-1LL):(1LL)) * g[dp[20][i]] + mod) % mod;
}
printf("%lld\n", ans);
return 0;
}
京公网安备 11010502036488号