#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 20;
int n, q;
string s, t;
int dp[(1 << maxN) + 2];
int f[(1 << maxN) + 2];
int cnt[(1 << maxN) + 2];
inline int inv(int i){
return ((1 << n) - 1) ^ i;
}
void Init(){
cin >> n >> q >> s;
for (int i = 0; i < int(s.length()); ++i){
dp[i] = s[i] - '0';
f[inv(i)] = dp[i];
}
for (int i = 0; i < n; ++i){
for (int j = 1; j < 1 << n; ++j){
if (j & (1 << i)){
dp[j] += dp[j ^ (1 << i)];
}
}
}
for (int i = 0; i < n; ++i){
for (int j = 0; j < 1 << n; ++j){
if (j & (1 << i)){
f[j] += f[j ^ (1 << i)];
}
}
}
for (int i = 1; i < 1 << n; ++i){
int j = i & -i;
cnt[i] = cnt[i ^ j] + 1;
}
while (q--){
cin >> t;
vector <int> A, B, C;
vector <int> val((1 << n) + 1, 0);
for (int i = 0; i < int(t.length()); ++i){
if (t[i] == '0') A.pb(n - i - 1);
if (t[i] == '1') B.pb(n - i - 1);
if (t[i] == '?') C.pb(n - i - 1);
}
int x = A.size(), y = B.size(), z = C.size();
if (x <= 6){
int tem = 0, ans = 0;
for (int i: C) tem += 1 << i;
for (int i = 1; i < 1 << x; ++i){
int t = i & -i;
val[i] = val[i ^ t] + (1 << A[__lg(t)]);
}
for (int i = 0; i < 1 << x; ++i){
if ((x & 1) ^ (cnt[i] & 1)) ans -= f[val[i] + tem];
else ans += f[val[i] + tem];
}
cerr << ans << "\n";
}
else if (y <= 6){
int tem = 0, ans = 0;
for (int i: C) tem += 1 << i;
for (int i = 1; i < 1 << y; ++i){
int t = i & -i;
val[i] = val[i ^ t] + (1 << B[__lg(t)]);
}
for (int i = 0; i < 1 << y; ++i){
if ((y & 1) ^ (cnt[i] & 1)) ans -= dp[val[i] + tem];
else ans += dp[val[i] + tem];
}
cerr << ans << "\n";
}
else{
//brute all ?s
for (int i = 1; i < 1 << z; ++i){
int t = i & -i;
val[i] = val[i ^ t] + (1 << C[__lg(t)]);
}
int tem = 0, ans = 0;
for (int i: B) tem += 1 << i;
for (int i = 0; i < 1 << z; ++i){
ans += s[val[i] + tem] - '0';
}
cout << ans << "\n";
}
}
}
int main(){
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
//freopen(taskname".out", "w", stdout);
}
faster;
ll tt = 1;
//cin >> tt;
while (tt--){
Init();
}
}
Compilation message
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
118 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
