LOJ2351「JOI 2018 Final」毒蛇越狱 容斥+子集卷积

题面

题目传送门

解法

• 暴力显然是枚举$?$到底填什么，那么单次询问的复杂度为$O(2^{cn{t}_{?}})$，并没有什么可以优化的地方。
• 不妨考虑一个容斥，将$?$全部看作是$1$，然后求子集的权值和。但是我们会将某些位置强制为$1$却填成$0$的数算入答案，那么我们还要减去这部分的答案。容斥的复杂度为$O(2^{cn{t}_1})$。
• 可以发现，因为$n$只到$20$，所以$\min (cn{t}_0,cn{t}_1,cn{t}_{?})$至多只有$6$。那么我们只要看哪一个最小然后相应地容斥或者暴力枚举即可。
• 时间复杂度：$O(n\times 2^n+2^{\lfloor \frac{n}{3}\rfloor }\times q)$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;
}
const int N = 1 << 20;
int cnt[N], val[N], s[N][2];
int main() {
	int n, q; read(n), read(q); int m = (1 << n) - 1, t = n / 3;
	for (int i = 1; i <= m; i++) cnt[i] = cnt[i - (i & -i)] + 1;
	for (int i = 0; i <= m; i++) {
		char c = getchar();
		while (!isdigit(c)) c = getchar();
		s[i][0] = s[i][1] = val[i] = c - '0';
	}
	for (int j = 0; j < n; j++)
		for (int i = 0; i <= m; i++)
			if ((i >> j) & 1) s[i][0] += s[i ^ (1 << j)][0], s[i ^ (1 << j)][1] += s[i][1];
	while (q--) {
		int s0 = 0, s1 = 0, s2 = 0, ans = 0;
		char st[30]; scanf(" %s", st);
		for (int i = 0, j = n - 1; i < n; i++, j--)
			if (st[i] == '0') s0 |= (1 << j);
				else if (st[i] == '1') s1 |= (1 << j);
					else s2 |= (1 << j);
		if (cnt[s0] <= t) {
			for (int ts = s0; ; ts = s0 & (ts - 1)) {
				(cnt[ts] & 1) ? ans -= s[s1 | ts][1] : ans += s[s1 | ts][1];
				if (!ts) break;
			}
		} else if (cnt[s1] <= t)
			for (int ts = s1; ; ts = s1 & (ts - 1)) {
				(cnt[ts ^ s1] & 1) ? ans -= s[s2 | ts][0] : ans += s[s2 | ts][0];
				if (!ts) break;
			}
		else
			for (int ts = s2; ; ts = s2 & (ts - 1)) {
				ans += val[s1 | ts];
				if (!ts) break;
			}
		cout << ans << 'n';
	}
	return 0;
}

最后

以上就是隐形芝麻为你收集整理的LOJ2351「JOI 2018 Final」毒蛇越狱 容斥+子集卷积的全部内容，希望文章能够帮你解决LOJ2351「JOI 2018 Final」毒蛇越狱 容斥+子集卷积所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。