#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> li;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
int main(){
ios::sync_with_stdio(false);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int L, Q; cin>>L>>Q;
string s; cin >> s;
int dp[1<<L]; FOR(i,0,(1<<L)) dp[i]=s[i]-'0';
int dp2[1<<L]; FOR(i,0,(1<<L)) dp2[i]=s[(1<<L)-1-i]-'0';
FOR(i,0,L){
FOR(mask,0,(1<<L)){
if (mask & (1<<i)) {dp[mask] += dp[mask-(1<<i)]; dp2[mask] += dp2[mask-(1<<i)];}
}
}
FOR(i,0,Q){
string t; cin >> t; reverse(t.begin(), t.end());
int cnt1=0, cnt2=0; FOR(j,0,L) {cnt1 += (t[j]=='?'); cnt2 += (t[j]=='1');}
if (cnt1 <= 6){
int ans = 0;
vi a; int cur = 0;
FOR(j,0,L){
if (t[j]=='?') a.pb(j);
else cur += (1<<j)*(t[j]-'0');
}
FOR(j,0,(1<<cnt1)){
int val=0; FOR(k,0,cnt1){
if (j & (1<<k)) val ^= (1<<a[k]);
}
//cout<<cur+val<<" ";
ans+=s[cur^val]-'0';
}
cout<<ans<<'\n'; continue;
}
if (cnt2 <= 6){
vi a; int cur=0;
FOR(j,0,L){
if (t[j]=='1') {a.pb(j); cur += (1<<j);}
if (t[j]=='?') cur += (1<<j);
}
int ans = 0;
FOR(j,0,(1<<cnt2)){
int val=0; int num=0; FOR(k,0,cnt2){
if (j & (1<<k)) {val ^= (1<<a[k]); num^=1;}
}
if (num) ans += dp[cur^val];
else ans -= dp[cur^val];
}
cout<<ans<<'\n'; continue;
}
int cnt3=L-cnt1-cnt2; vi a; int cur=0;
FOR(j,0,L){
if (t[j] != '1') cur+= (1<<j);
if (t[j] == '0') a.pb(j);
}
int ans=0;
FOR(j,0,(1<<cnt3)){
int val=0,num=0; FOR(k,0,cnt3){
if (j & (1<<k)) {val ^= (1<<a[k]); num^=1;}
}
if (num) ans-=dp2[cur^val];
else ans+=dp2[cur^val];
}
cout<<ans<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
