自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 22:32:02，当前版本为作者最后更新于2021-11-22 16:14:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一种经典的做法，题解里竟然没有。

设 $S$ 中 $0,1,\texttt{?}$ 的个数分别为 $a,b,c$。

算法一：暴力将每个 $\texttt{?}$ 换成 $0$ 或 $1$ 求和，时间复杂度 $O(2^c)$。

算法二：对 $0$ 容斥，也就是写成 $(\times s(0))=(\times (s(\texttt{?})-s(1)))$ 的形式，将每个 $0$ 换成 $\texttt{?}$ 和 $1$，而对于只有 $\texttt{?}$ 和 $1$ 的情况可以直接预处理高维后缀和后计算，时间复杂度 $O(2^a)$。

算法三：对 $1$ 容斥，过程同上，用高维前缀和计算，时间复杂度 $O(2^b)$。

选取最优的算法，单次询问时间复杂度 $O(\min(2^a,2^b,2^c))$，而由于 $a+b+c=n$ 所以我们有 $\min(a,b,c)\leq \dfrac{n}{3}$，加上高维前后缀和的复杂度，总的时间复杂度为 $O(q2^{\frac{n}{3}}+n\times 2^n)$。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1200010;
int l,q,ans,cnt0,cnt1,cntq,sz0,sz1,cq[30],c0[30],c1[30],a[MAXN],b[MAXN],c[MAXN];
char t[30],s[MAXN];
void dfsq (int x,int msk) {
	if (x==cntq+1) {ans+=a[msk];return;}
	dfsq(x+1,msk);
	dfsq(x+1,msk|(1<<cq[x]));
	return;
}
void dfs0 (int x,int flg,int msk) {
	if (x==cnt0+1) {ans+=c[msk]*flg;return;}
	dfs0(x+1,flg,msk);
	dfs0(x+1,-flg,msk|(1<<c0[x]));
	return;
}
void dfs1 (int x,int flg,int msk) {
	if (x==cnt1+1) {ans+=b[msk]*flg;return;}
	dfs1(x+1,flg,msk|(1<<c1[x]));
	dfs1(x+1,-flg,msk);
	return;
} 
int main () {
	scanf("%d%d%s",&l,&q,s+1);
	for (int i=0;i<(1<<l);i++) {a[i]=b[i]=c[i]=s[i+1]-'0';}
	for (int i=1;i<(1<<l);i<<=1) {
		for (int j=0;j<(1<<l);j+=(i<<1)) {
			for (int k=0;k<i;k++) {b[i+j+k]+=b[j+k];}
		}
	}
	for (int i=1;i<(1<<l);i<<=1) {
		for (int j=0;j<(1<<l);j+=(i<<1)) {
			for (int k=0;k<i;k++) {c[j+k]+=c[i+j+k];}
		}
	}
	for (int i=1;i<=q;i++) {
		scanf("%s",t+1);
		for (int i=1;i<=l/2;i++) {swap(t[i],t[l-i+1]);}
		cnt0=0,cnt1=0,cntq=0,sz0=0,sz1=0;
		for (int i=0;i<l;i++) {
			if (t[i+1]=='0') {c0[++cnt0]=i;}
			else if (t[i+1]=='1') {c1[++cnt1]=i,sz1|=(1<<i);}
			else {cq[++cntq]=i,sz0|=(1<<i);}
		}
		ans=0;
		if (cntq<=6) {dfsq(1,sz1);}
		else if (cnt0<=6) {dfs0(1,1,sz1);}
		else {dfs1(1,1,sz0);}
		printf("%d\n",ans);
	}
	return 0;
}