洛谷题解

#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;///test
}