大意: 给定集合a, 求a的按位与和等于0的非空子集数.
首先由容斥可以得到 $ans = \sum \limits_{0\le x <2^{20}} (-1)^{\alpha} f_x$,
其中$\alpha$为$x$二进制中$1$的个数, $f_x$表示与和等于$x$的非空子集数.
$f_x$是一个$20$维前缀和, 按传统容斥做法的话显然要超时, 可以每次求一维的和, 再累加
比方说对于2维前缀和, 用容斥的求法是这样
for (int i=1; i<=n; ++i) {
for (int j=1; j<=n; ++j) {
s[i][j] += s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
优化后就是这样的
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
s[i][j] += s[i][j-1];
}
}
for (int j=1; j<=m; ++j) {
for (int i=1; i<=n; ++i) {
s[i][j] += s[i-1][j];
}
}
本题的代码如下
#include <iostream>
#include <algorithm>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
const int N = (1<<20)-1, P = 1e9+7;
int n, a[N+10], pow2[N+10];
int main() {
scanf("%d", &n);
REP(i,1,n) {
int t;
scanf("%d", &t);
++a[t];
}
pow2[0] = 1;
REP(i,1,N) pow2[i]=pow2[i-1]*2%P;
REP(j,0,19) REP(i,0,N) {
if (i>>j&1) (a[i^(1<<j)]+=a[i])%=P;
}
int ans = 0;
REP(i,0,N) {
int sign = 1;
for (int j=i; j; j^=j&-j) sign=-sign;
(ans+=(sign*(pow2[a[i]]-1)+P)%P)%=P;
}
printf("%d\n", ans);
}
Jzzhu and Numbers CodeForces - 449D (高维前缀和,容斥)
原文：https://www.cnblogs.com/uid001/p/10430314.html