# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1124428 | Muaath_5 | Snake Escaping (JOI18_snake_escaping) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#pragma GCC target("popcnt")
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 20, SPLIT = 6;
int n, q, mask[1<<N];
string vals;
int dp[2][1<<N];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> q >> vals;
for (int i = 0; i < (1<<n); i++) {
dp[0][msk] = dp[1][msk] = mask[i] = vals[i] - '0';
}
for (int i = 0; i < n; i++) {
for (int msk = 0; msk < (1<<n); msk++) {
if (msk & (1 << i))
dp[0][msk] += dp[0][msk ^ (1 << i)];
else
dp[1][msk] += dp[1][msk ^ (1 << i)];
}
}
while (q--) {
string b;
cin >> b;
int c_marks=0, cc[2]={};
for (char c : b)
if (c == '?')
c_marks++;
else
cc[c-'0']++;
if (c_marks <= SPLIT) {
int init = 0;
int marks = 0;
for (int i = 0; i < n; i++)
if (b[i] == '1')
init |= (1 << (n-i-1));
else if (b[i] == '?')
marks |= (1 << (n-i-1));
int ans = 0;
for (int msk = marks; msk >= 0; msk = (msk-1)&marks) {
ans += mask[init | msk];
if (msk == 0) break;
}
cout << ans << '\n';
continue;
}
int x = (cc[1] <= SPLIT ? 0 : 1);
int init = 0;
int marks = 0;
for (int i = 0; i < n; i++) {
if (b[i] == '?' && x == 0)
init |= (1 << (n-i-1));
if (b[i] == '1' && x == 1)
init |= (1 << (n-i-1));
if (x == 0 && b[i] == '1')
marks |= (1 << (n-i-1));
if (x == 1 && b[i] == '0')
marks |= (1 << (n-i-1));
}
int ans = 0;
for (int msk = marks; msk >= 0; msk = (msk-1)&marks) {
if (__builtin_popcount(msk)%2 == cc[x] % 2)
ans += dp[x][init | msk];
else
ans -= dp[x][init | msk];
if (msk == 0) break;
}
cout << abs(ans) << '\n';
}
}