| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1300390 | StefanSebez | Snake Escaping (JOI18_snake_escaping) | C11 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=(1<<20)+50;
int L,q;
int f[N],F0[N],F1[N];
int main(){
scanf("%i%i",&L,&q);
string s;cin>>s;
int n=1<<L;
//SOS dp
for(int i=0;i<n;i++) F0[i]=F1[i]=f[i]=s[i]-'0';
for(int i=0,e=1;i<L;i++,e<<=1){
for(int mask=0;mask<n;mask++){
if(mask&e) F0[mask]+=F0[mask^e];
}
for(int mask=n-1;mask>=0;mask--){
if(!(mask&e)) F1[mask]+=F1[mask^e];
}
}
while(q--){
string t;cin>>t;
int cnt[3]={0};
for(auto c:t){
if(c=='0')cnt[0]++;
if(c=='1')cnt[1]++;
if(c=='?')cnt[2]++;
}
ll res=0;
if(cnt[1]<=L/3){
int mask0=0,mask1=0;
for(int i=L-1,e=1;i>=0;i--,e<<=1){
if(t[i]=='?')mask0^=e;
if(t[i]=='1')mask1^=e;
}
for(int mask=mask1;mask>=0;mask=(mask-1)&mask1){
if(__builtin_popcount(mask)%2==__builtin_popcount(mask1)%2)res+=F0[mask0^mask];
else res-=F0[mask0^mask];
if(mask==0)break;
}
}
else if(cnt[0]<=L/3){
int mask0=0,mask1=0;
for(int i=L-1,e=1;i>=0;i--,e<<=1){
if(t[i]!='?')mask0^=e;
if(t[i]=='1'||t[i]=='?')mask1^=e;
}
for(int mask=mask1;mask<n;mask=(mask+1)|mask1){
if(__builtin_popcount(mask)%2==__builtin_popcount(mask1)%2)res+=F1[mask0&mask];
else res-=F1[mask0&mask];
}
}
else{
int mask0=0,mask1=0;
for(int i=L-1,e=1;i>=0;i--,e<<=1){
if(t[i]=='1')mask0^=e;
if(t[i]=='?')mask1^=e;
}
for(int mask=mask1;mask>=0;mask=(mask-1)&mask1){
res+=f[mask0^mask];
if(mask==0)break;
}
}
printf("%lld\n",res);
}
return 0;
}