/// 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 rep(i, l, r) for (int i = (l); i < (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#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)(1 << 20) + 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 L = 7;
int n, q;
char s[N];
char t[N][20];
int add_id;
int tmr;
int was[20][1594323];
int dp[20][1594323];
int a[1594323][13];
ll pw[20];
inline int calc(int v, int mask, int nmask) {
if (v == n) {
return s[nmask + add_id] - '0';
}
if (was[v][mask] == tmr) return dp[v][mask];
was[v][mask] = tmr;
if (a[mask][v - L] == 2) {
return dp[v][mask] = calc(v + 1, mask - pw[v - L], nmask + (1 << v)) + calc(v + 1, mask - (pw[v - L] << 1), nmask);
}
if (a[mask][v - L] == 1) {
return dp[v][mask] = calc(v + 1, mask, nmask + (1 << v));
}
return dp[v][mask] = calc(v + 1, mask, nmask);
}
/// 3 ^ 0 * q0 + 3 ^ 1 * q1 + 3^2 * q2 = n
/// 7 = 3 ^ 1 * 2 + 3^0 * 1
/*
3 ^ 2 * q2 + 3 ^ 1 * q1 + 3 ^ 0 * q0
*/
int mem[1 << 7][2187];
int hsh[N];
bool good(int mask, int id) {
if (~mem[mask][hsh[id]]) return mem[mask][hsh[id]];
rep(i, 0, L) {
if (t[id][i] != '?') {
if (t[id][i] == '0' && (mask & (1 << i))) return mem[mask][hsh[id]] = 0;
if (t[id][i] == '1' && !(mask & (1 << i))) return mem[mask][hsh[id]] = 0;
}
}
return mem[mask][hsh[id]] = 1;
}
int ans[N];
int main() {
#ifdef IOI2018
freopen ("in.txt", "r", stdin);
#endif
Kazakhstan
cin >> n >> q >> s;
rep(i, 0, q) {
cin >> t[i];
reverse(t[i], t[i] + n);
int h = 0;
rep(j, L, n) {
if (t[i][j] == '?') h = h * 3 + 2;
else if (t[i][j] == '1') h = h * 3 + 1;
else h = h * 3;
}
rep(j, L, n) {
if (t[i][j] == '?') a[h][j - L] = 2;
else if (t[i][j] == '1') a[h][j - L] = 1;
}
}
L = min(n, L);
rep(i, 0, q) {
rep(j, 0, L) {
if (t[i][j] == '?') hsh[i] = hsh[i] * 3 + 2;
else if (t[i][j] == '1') hsh[i] = hsh[i] * 3 + 1;
else hsh[i] = hsh[i] * 3;
}
}
pw[0] = 1;
memset(mem, -1, sizeof(mem));
rep(i, 1, 20) pw[i] = pw[i - 1] * 3;
rep(mask, 0, (1 << L)) {
++tmr;
rep(i, 0, q) {
if (good(mask, i)) {
if (n <= L) {
ans[i] += s[mask] - '0';
}
else {
int st = 0;
per(j, n - 1, L) {
if (t[i][j] == '?') st = st * 3 + 2;
else if (t[i][j] == '1') st = st * 3 + 1;
else st *= 3;
}
add_id = mask;
ans[i] += calc(L, st, 0);
}
}
}
}
rep(i, 0, q) cout << ans[i] << nl;
ioi
}
Compilation message
snake_escaping.cpp: In function 'bool good(int, int)':
snake_escaping.cpp:82:72: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
if (t[id][i] == '0' && (mask & (1 << i))) return mem[mask][hsh[id]] = 0;
~~~~~~~~~~~~~~~~~~~^~~
snake_escaping.cpp:83:73: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
if (t[id][i] == '1' && !(mask & (1 << i))) return mem[mask][hsh[id]] = 0;
~~~~~~~~~~~~~~~~~~~^~~
snake_escaping.cpp:86:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
return mem[mask][hsh[id]] = 1;
~~~~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
