luogu CF449D Jzzhu and Numbers
luogu CF449D Jzzhu and Numbers
题目大意 求从 { a i } \{ ai \} {ai} 里面选出一个非空子集使这些数按位与起来为0的方案数
题解 方案数？？？
DP？？？
数据范围这么大？？！！
不可做
考虑求问题的补集，and值不为0的有多少个
发现好像不是很好求
【luogu CF449D Jzzhu and Numbers】考虑DP
设f [ S ] 表 示 a n d 值 包 含 i 的 个 数 f[S]表示and值包含i的个数 f[S]表示and值包含i的个数
很容易发现f [ S ] = ∑ j = 0 20 f [ S ∣ ( 1 < < j ) ] f[S] = \sum\limits_{j=0}^{20}f[S | (1<
那怎么求不为0的方案数呢？
考虑容斥
按照二进制1出现的次数来容斥
然后这题就没了
#include
#define int long long
#define mod 1000000007
#define N 8000005
using namespace std;
int qpow(long long x, int y){
long long ret = 1;
for(;
y;
y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
return ret;
}
void fwt(int *a, int len, int opt){
for(int j = 0;
j <= 20;
j ++)
for(int i = 0;
i < len;
i ++)
if(!((1 << j) & i)) a[i] = (a[i] + opt * a[i | (1 << j)] + mod) % mod;
}
int pw[N], f[N], a[N], n;
main(){
scanf("%lld", &n);
for(int i = 1;
i <= n;
i ++)
scanf("%lld", &a[i]);
for(int i = 1;
i <= n;
i ++) f[a[i]] ++;
fwt(f, 1 << 20, 1);
for(int i = 0;
i < (1 << 20);
i ++) f[i] = qpow(2, f[i]);
long long ans = 0;
for(int i = 0;
i < (1 << 20);
i ++){
int bit = 0;
for(int j = 0;
j <= 20;
j ++)bit += (i >> j) & 1;
if(bit & 1) ans -= f[i];
else ans += f[i];
ans = (ans + mod) % mod;
}
printf("%lld", ans);
return 0;
} 推荐阅读
- 矩阵快速幂-CodeForces 450B Jzzhu and Sequences
- CodeForces - 450B Jzzhu and Sequences 规律
- [逆元]|[逆元] luogu 4942
- 【线性求逆元板子】|【线性求逆元板子】 luogu 3811
- [exgcd算最值]|[exgcd算最值] luogu 3951
- Luogu|Luogu 5170 【模板】类欧几里得算法
- ACM|Jzzhu and Sequences(CF #257 Div. 2)
- Codeforces|Codeforces 450B Jzzhu and Sequences(递推找规律)
- 扩展欧几里得例题(luogu_1082)
- 题解|Jzzhu and Sequences(规律，矩阵)