实现方法为枚举。先枚举替换串，再把替换串逐个插入,详见注释

#include<bits/stdc++.h>
using namespace std;
#define pb push_back() 
const int N=2e6+5;
int L,Q;
string s;
long long pre[N],suf[N],md[N],val[N],f[N]; 

int main(){
	cin>>L>>Q;
	cin>>s; int n=s.length();
	for(int i=0; i<n; i++)
		pre[i]=suf[i]=f[i]=s[i]-'0';
	for(int i=0; i<L; i++){//按维求和
		for(int j=0; j<n; j++)
			if((j>>i)&1) pre[j]+=pre[j^(1<<i)]; //高维前缀和 
		for(int j=n-1; j>=0; j--)
			if(!((j>>i)&1)) suf[j]+=suf[j^(1<<i)];//高维后缀和	
	}
	for(int i=1; i<=Q; i++){
		string T; cin>>T;
		int a=0,b=0,c=0,A=0,B=0; long long ans=0;
		for(int j=0; j<L; j++) {
			if(T[L-j-1]=='?') md[j]=2,a++,A+=(1<<j);
			if(T[L-j-1]=='1') md[j]=1,b++,B+=(1<<j);
			if(T[L-j-1]=='0') md[j]=0,c++;
		}
		if(a<=b&&a<=c){  //枚举？ 
			for(int j=0; j<(1<<a); j++){//枚举填充的数
				int Snk=B;//待填充数
				for(int k=0,p=0; k<a; k++){//填充
					while(p<=L-1&&md[p]!=2) p++;//不填？以外的空
					if(p==L) break;
					long long op=(j>>k)&1;
					Snk+=op*(1<<p); 
				}
				ans+=f[Snk]; 
			}
		}
		else if(b<=c&&b<=a){  //将1容斥为?-0
			for(int j=0; j<(1<<b); j++){ // 1=？ 0=0 
				int Snk=A,d=0;//d为容斥系数
				for(int k=0; k<b; k++) d+=(((j>>k)&1)^1);
				for(int k=0,p=0; k<b; k++){
					while(p<=L-1&&md[p]!=1) p++;
					if(p==L) break;
					long long op=(j>>k)&1;
					Snk+=op*(1<<p);
				}  
				ans+=((d&1) ? -1ll : 1ll)*pre[Snk];
		//		cout<<((d&1) ? -1 : 1)<<" "<<Snk<<"\n";
			}
		}
		else{ //将0容斥为?-1
			for(int j=0; j<(1<<c); j++){ //1=1 0=?
				int Snk=B,d=0;
				for(int k=0; k<c; k++) d+=((j>>k)&1);
				for(int k=0,p=0; k<c; k++){
					while(p<=L-1&&md[p]!=0) p++;
					if(p==L) break;
					long long op=(j>>k)&1;
					Snk+=op*(1<<p);
				}
				ans+=((d&1) ? -1ll : 1ll)*suf[Snk];
			//	cout<<((d&1) ? -1 : 1)<<" "<<Snk<<"\n";
			}
		} 
		cout<<(ans>0 ? ans : -ans)<<"\n";
	}
}