CF449D Jzzhu and Numbers
原题链接
首先我们让 \(c_s\) 表示有多少 \(a_i\) 是 \(s\) 的超集，那么有：取与后是 \(s\) 的超集的集合个数 \(f_s=2^{c_i}\)。
再让 \(g_s\) 表示有多少集合取与后恰好是 \(s\)，那么显而易见 \(g_0\) 就是答案。并且有：
\[f_s=\sum_{s \subseteq t} g_t
\]
\[g_s=\sum_{s \subseteq t}(-1)^{|t|-|s|}f_t
\]
点击查看代码
#include <bits/stdc++.h>
#define L(i, a, b) for(int i = a; i <= b; i++)
#define R(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, ans, U, a[N], p[N], c[1 << 20];
int main(){
scanf("%d", &n), U = (1 << 20) - 1, p[0] = 1;
L(i, 1, n) scanf("%d", &a[i]), c[a[i]]++, p[i] = p[i - 1] * 2 % mod;
L(i, 1, 20) L(s, 0, U) if(s & (1 << i - 1))
c[s ^ (1 << i - 1)] += c[s], c[s ^ (1 << i - 1)] %= mod;
L(s, 0, U){
if(__builtin_popcount(s) & 1) ans -= p[c[s]], ans %= mod;
else ans += p[c[s]], ans %= mod;
}
printf("%d\n", (ans + mod) % mod);
return 0;
}