/// In The Name Of God
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define nl '\n'
#define ioi exit(0);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = (int)5e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using namespace std;
int n, q;
int a[N];
int now[N];
int dp1[1 << 27];
int bp(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res *= x;
x *= x, y >>= 1;
}
return res;
}
int p[N];
int rec1(int v = 0, int mask = 0) {
if (v == n) return a[mask];
if (p[v] < 2) return rec1(v + 1, mask | (1 << v) * p[v]);
int res = 0;
for (int i = 0; i <= 1; i++) {
res += rec1(v + 1, mask | (1 << v) * i);
}
return res;
}
void rec(int v = 0, int now = 0) {
if (v == n) {
dp1[now] += rec1();
return;
}
for (int i = 0; i <= 2; i++) {
p[v] = i;
rec(v + 1, now + bp(3, v) * i);
}
}
void solve() {
int mask = 0;
for (int i = n - 1; i >= 0; i--) {
char x;
cin >> x;
if (x == '?') now[i] = 2;
else now[i] = x - '0';
mask += now[i] * bp(3, i);
}
cout << dp1[mask] << nl;
}
int main() {
#ifdef IOI2018
freopen ("in.txt", "r", stdin);
#endif
cin >> n >> q;
for (int i = 0, j = (1 << n); i < j; i++) {
char x;
cin >> x;
a[i] = x - '0';
}
rec();
for (int i = 1; i <= q; i++) {
solve();
}
ioi
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
