#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll l, q;
string s;
ll totzero = 0;
ll a = 13, b = 7;
ll sum[(1<<13)+10][(1<<7)+10];
ll p3[30];
void precalc(ll step, ll num, ll val, ll idx, ll add){
if(step == b){
sum[idx][val] += add;
return;
}
precalc(step+1, num/2, val+(num%2)*p3[step], idx, add);
precalc(step+1, num/2, val+2*p3[step], idx, add);
}
unordered_map<ll, ll> dp[23][(1<<13)+10];
ll v2;
ll calc(ll step, ll idx, ll val){
if(dp[step][idx][val] != 0){
return dp[step][idx][val]-1;
}
if(step == a || step == s.size()){
//cout << s << '\n' << idx << '\n';
dp[step][idx][val] = sum[idx][v2]+1;
return dp[step][idx][val]-1;
}
dp[step][idx][val] = 1;
if(s[step] != '1')
dp[step][idx][val] += calc(step+1, idx, val/3);
if(s[step] != '0')
dp[step][idx][val] += calc(step+1, idx+(1LL<<step), val/3);
return dp[step][idx][val]-1;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
p3[0] = 1;
for(ll i = 1; i < 30; ++i)
p3[i] = 3*p3[i-1];
cin >> l >> q;
ll n = (1<<l);
cin >> s;
for(ll i = 0; i < n; ++i){
ll v1 = (i&((1<<a)-1));
precalc(0, (i>>a), 0, v1, s[i]-'0');
}
for(ll i = 0; i < q; ++i){
cin >> s;
reverse(s.begin(), s.end());
ll v1 = 0;
for(ll i = 0; i < s.size(); ++i){
if(s[i] == '1')
v1 += p3[i];
else if(s[i] == '?')
v1 += 2*p3[i];
}
v2 = 0;
for(ll i = a; i < s.size(); ++i){
if(s[i] == '1')
v2 += p3[i-a];
else if(s[i] == '?')
v2 += 2*p3[i-a];
}
cout << calc(0, 0, v1) << '\n';
}
}
Compilation message
snake_escaping.cpp: In function 'll calc(ll, ll, ll)':
snake_escaping.cpp:34:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(step == a || step == s.size()){
~~~~~^~~~~~~~~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:70:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i = 0; i < s.size(); ++i){
~~^~~~~~~~~~
snake_escaping.cpp:77:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i = a; i < s.size(); ++i){
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
