This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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++)
mask[i] = vals[i] - '0';
for (int i = 0; i <= n; i++) {
for (int msk = 0; msk < (1<<n); msk++) {
if(!i){
dp[0][msk] = mask[msk];
dp[1][msk] = mask[msk];
continue;
}
if (msk & (1 << (i-1)))
dp[0][msk] += dp[0][msk ^ (1 << (i-1))];
else
dp[1][msk] += dp[1][msk ^ (1 << (i-1))];
}
}
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';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |