CF449D Jzzhu and Numbers题解

令

AND

表示若干个数

&

起来的结果。

令

x

被

y

包含表示

x & y == y

直接设状态不好做。

于是转变思路。

令

h_i

表示

AND

被

i

包含的所有

AND

的方案数。

则答案可以由

h_i

容斥得到。

由于只关心

h_i

中

i

在二进制下有几个

1

，所以简化成代码中的

g_i

, 表示有

i

个

1

。

问题转化成如何求

h_i

。事实上只需求出

f_i

, 表示有多少个

a_x

被

i

包含。

h_i = 2 ^ {f_i} - 1

。减一是因为要除去空集。

f_i

显然可以

SOSdp

求得。

代码如下 :

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 20) + 100;
const int Mod = 1e9 + 7;
int n, res, a[N], f[N], g[N], _2[N];
inline void upd(int &x, int y) {
	x += y;
	if(x >= Mod) x -= Mod;
	if(x < 0) x += Mod;
	return;
}
signed main() {
	ios :: sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	_2[0] = 1;
	for(int i = 1; i < (1 << 20); ++i) _2[i] = _2[i - 1] * 2 % Mod;
	for(int i = 1; i <= n; ++i) cin >> a[i], ++f[a[i]];
	for(int j = 0; j < 20; ++j)
		for(int i = (1 << 20) - 1; ~i; --i)
			if(i >> j & 1) upd(f[i ^ (1 << j)], f[i]);
	for(int i = 0; i < (1 << 20); ++i) upd(g[__builtin_popcount(i)], _2[f[i]] - 1);
	for(int i = 0; i < 20; ++i) {
		if(i & 1) upd(res, -g[i]);
		else upd(res, g[i]);
	}
	cout << res << '\n';
	return 0;
}

CF449D Jzzhu and Numbers题解

文章操作

相关推荐

评论

CF449D Jzzhu and Numbers题解