题解：P7670 [JOI 2018 Final] 毒蛇越狱 / Snake Escaping

#include<bits/stdc++.h>
using namespace std;
namespace IO {
    static const string name = "disinfect", suf_in = "in", suf_out = "out";
    static constexpr int S = (1 << 21), dgt = 2, ir = 1; char b[S], *p1 = b, *p2 = b, pb[S], *p = pb; void Fl() { fwrite(pb, 1, p - pb, stdout), p = pb; }
#define _r return *this
    struct Fr { bool _b(char c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t'; } char gc() { if (p1 == p2) p2 = (p1 = b) + fread(b, 1, S, stdin); return p1 == p2 ? ' ' : *p1++; } template <class T> Fr &operator>>(T &x) { char c = gc(); T f = 1; for (x = 0; !isdigit(c);) { if(c == '-') f = -1; c = gc(); } while (isdigit(c)) x = (x * 10) + (c ^ 48), c = gc(); x *= f; _r; } Fr &operator>>(char *s) { int l = 0; char c; operator>>(c); for (; !_b(c); s[l++] = c, c = gc()) ; s[l] = '\0'; _r; } Fr &operator>>(string &s) { s = ""; char c = gc(); while(_b(c)) c = gc(); while(!_b(c)) s += c, c = gc(); _r; } Fr &operator>>(double &x) { double t = 1, s = 0; char c = gc(); for (x = 0; !isdigit(c); c = gc()) s = (c == '-'); for (; isdigit(c); c = gc()) x = x * 10 + (c - 48); if (c == '.') for (c = gc(); isdigit(c); c = gc()) x += (t /= 10.0) * (c - 48), s && (x = -x); _r; } Fr &operator>>(char &c) { do c = gc(); while (_b(c)); _r; } } cin;
    struct Fw { void pt(char c) { *p++ = c; if (p - pb == S) Fl(); } template <class T> Fw &operator<<(T x) { if (!x) { pt(48); _r; } x < 0 && (pt('-'), x = -x); int s[64], t = 0; while (x) s[++t] = x % 10, x /= 10; while (t) pt(s[t--] + 48); _r; } Fw &operator<<(char c) { pt(c); _r; } Fw &operator<<(const char *s) { operator<<((char *)s); _r; } Fw &operator<<(char *s) { int c = 0; while (s[c]) pt(s[c++]); _r; } Fw &operator<<(double x) { int k = 0; x < 0 && (pt('-'), x = -x), ir && (x += 5 * pow(10, -dgt - 1)), operator<<(int(x)), pt('.'), x -= int(x); while (k++ < dgt) pt(int(x *= 10) + 48), x -= int(x); _r; } Fw &operator<<(string s) { for(int i = 0; s[i] != '\0'; ++i) pt(s[i]); _r; } ~Fw() { Fl(); } } cout;
    struct fileIO { fileIO() { freopen((name + "." + suf_in).c_str(), "r", stdin), freopen((name + "." + suf_out).c_str(), "w", stdout); } } ;
};
#define cin IO::cin
#define cout IO::cout
const int N=21;

int f[1<<N],g[1<<N]; 

int p[1<<N];

int n,q,ans;

string s;

char c;

void fwt(int f[],int n){
	for(int i=1;i<=n;i*=2){
		for(int j=0;j<n;j+=i*2){
			for(int k=j;k<j+i;k++)
			f[k+i]+=f[k];
		}
	}
}

void fwt1(int f[],int n){
	for(int i=1;i<=n;i*=2){
		for(int j=0;j<n;j+=i*2){
			for(int k=j;k<j+i;k++)
			f[k]+=f[k+i];
		}
	}
}

void dfs2(int u,int k){
	if(u==n){
		ans+=p[k];return ;
	}
	if(s[u]=='?'){
		dfs2(u+1,k);
		dfs2(u+1,k+(1<<u));
	}
	if(s[u]=='1')dfs2(u+1,k+(1<<u));
	if(s[u]=='0')dfs2(u+1,k);
}

void dfs0(int u,int k,int o){
	if(u==n){
		ans+=g[k]*o;return ;
	}
	if(s[u]=='0'){
		dfs0(u+1,k,o);
		dfs0(u+1,k+(1<<u),-1*o);
	}
	if(s[u]=='1')dfs0(u+1,k+(1<<u),o);
	if(s[u]=='?')dfs0(u+1,k,o);
}

void dfs1(int u,int k,int o){
	if(u==n){
		ans+=f[k]*o;return ;
	}
	if(s[u]=='1'){
		dfs1(u+1,k,-1*o);
		dfs1(u+1,k+(1<<u),o);
	}
	if(s[u]=='0')dfs1(u+1,k,o);
	if(s[u]=='?')dfs1(u+1,k+(1<<u),o);
}

signed main() {
	cin>>n>>q;
	for(int i=0;i<(1<<n);i++){
		cin>>c; 
		p[i]=c-'0';f[i]=p[i];g[i]=p[i];
	}
	fwt(f,1<<n);fwt1(g,1<<n);
	while(q--){
		cin>>s;ans=0;
		reverse(s.begin(),s.end()); 
		int a=0,b=0,c=0;
		for(char c1:s){
			if(c1=='0')a++;
			else if(c1=='1')b++;
			else c++;
		}int mn=min({a,b,c});
		if(mn==c)dfs2(0,0);
		else if(mn==a)dfs0(0,0,1);
		else if(mn==b)dfs1(0,0,1);
		cout<<ans<<"\n";
	}
	return 0;
}