#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e6+5;
const ll K=350;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
ll dp[N],l,po[N],q,k,ans[N];
string s,a;
vector<pll> que[1000];
ll get3(ll val,ll ip){
return (val/po[ip])%3;
}
void cal(ll id){
REP(i,po[k]){
ll tx=0;
REP(j,k){
if(get3(i,k-j-1)==2){
dp[i]=dp[i-2*po[k-j-1]]+dp[i-po[k-j-1]];
break;
}
tx=tx*2+get3(i,k-j-1);
if(j==k-1){dp[i]=s[(id<<k)+tx]-'0';}
}
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>l>>q>>s;
k=min(l,12LL);
po[0]=1;
REP1(i,k)po[i]=po[i-1]*3;
REP(T,q){
cin>>a;
ll tx=0;
for(int i=l-k;i<l;i++)tx=tx*3+(a[i]=='?'?2:a[i]-'0');
REP(i,(1<<(l-k))){
bool ck=1;
REP(j,l-k){
if(a[j]=='?')continue;
if((a[j]-'0')!=(i>>(l-k-j-1))){ck=0;break;}
}
if(ck){
que[i].pb(mp(tx,T));
}
}
}
REP(i,(1<<(l-k))){
if(SZ(que[i]))cal(i);
for(auto j:que[i]){
ans[j.Y]+=dp[j.X];
}
}
REP(i,q)cout<<ans[i]<<"\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
876 KB |
Output is correct |
2 |
Correct |
2 ms |
924 KB |
Output is correct |
3 |
Correct |
2 ms |
876 KB |
Output is correct |
4 |
Correct |
2 ms |
876 KB |
Output is correct |
5 |
Correct |
2 ms |
876 KB |
Output is correct |
6 |
Correct |
2 ms |
876 KB |
Output is correct |
7 |
Correct |
2 ms |
876 KB |
Output is correct |
8 |
Correct |
2 ms |
876 KB |
Output is correct |
9 |
Correct |
2 ms |
876 KB |
Output is correct |
10 |
Correct |
2 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
876 KB |
Output is correct |
2 |
Correct |
2 ms |
924 KB |
Output is correct |
3 |
Correct |
2 ms |
876 KB |
Output is correct |
4 |
Correct |
2 ms |
876 KB |
Output is correct |
5 |
Correct |
2 ms |
876 KB |
Output is correct |
6 |
Correct |
2 ms |
876 KB |
Output is correct |
7 |
Correct |
2 ms |
876 KB |
Output is correct |
8 |
Correct |
2 ms |
876 KB |
Output is correct |
9 |
Correct |
2 ms |
876 KB |
Output is correct |
10 |
Correct |
2 ms |
876 KB |
Output is correct |
11 |
Correct |
250 ms |
28472 KB |
Output is correct |
12 |
Correct |
266 ms |
28088 KB |
Output is correct |
13 |
Correct |
271 ms |
27448 KB |
Output is correct |
14 |
Correct |
236 ms |
27576 KB |
Output is correct |
15 |
Correct |
246 ms |
28472 KB |
Output is correct |
16 |
Correct |
251 ms |
27704 KB |
Output is correct |
17 |
Correct |
250 ms |
27576 KB |
Output is correct |
18 |
Correct |
212 ms |
29496 KB |
Output is correct |
19 |
Correct |
208 ms |
26552 KB |
Output is correct |
20 |
Correct |
273 ms |
28148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
876 KB |
Output is correct |
2 |
Correct |
2 ms |
924 KB |
Output is correct |
3 |
Correct |
2 ms |
876 KB |
Output is correct |
4 |
Correct |
2 ms |
876 KB |
Output is correct |
5 |
Correct |
2 ms |
876 KB |
Output is correct |
6 |
Correct |
2 ms |
876 KB |
Output is correct |
7 |
Correct |
2 ms |
876 KB |
Output is correct |
8 |
Correct |
2 ms |
876 KB |
Output is correct |
9 |
Correct |
2 ms |
876 KB |
Output is correct |
10 |
Correct |
2 ms |
876 KB |
Output is correct |
11 |
Correct |
250 ms |
28472 KB |
Output is correct |
12 |
Correct |
266 ms |
28088 KB |
Output is correct |
13 |
Correct |
271 ms |
27448 KB |
Output is correct |
14 |
Correct |
236 ms |
27576 KB |
Output is correct |
15 |
Correct |
246 ms |
28472 KB |
Output is correct |
16 |
Correct |
251 ms |
27704 KB |
Output is correct |
17 |
Correct |
250 ms |
27576 KB |
Output is correct |
18 |
Correct |
212 ms |
29496 KB |
Output is correct |
19 |
Correct |
208 ms |
26552 KB |
Output is correct |
20 |
Correct |
273 ms |
28148 KB |
Output is correct |
21 |
Correct |
309 ms |
40872 KB |
Output is correct |
22 |
Correct |
330 ms |
47924 KB |
Output is correct |
23 |
Correct |
303 ms |
35716 KB |
Output is correct |
24 |
Correct |
300 ms |
36144 KB |
Output is correct |
25 |
Correct |
316 ms |
42880 KB |
Output is correct |
26 |
Correct |
333 ms |
37124 KB |
Output is correct |
27 |
Correct |
321 ms |
36992 KB |
Output is correct |
28 |
Correct |
272 ms |
49924 KB |
Output is correct |
29 |
Correct |
250 ms |
30232 KB |
Output is correct |
30 |
Correct |
329 ms |
40284 KB |
Output is correct |
31 |
Correct |
318 ms |
39508 KB |
Output is correct |
32 |
Correct |
323 ms |
38276 KB |
Output is correct |
33 |
Correct |
282 ms |
42168 KB |
Output is correct |
34 |
Correct |
303 ms |
36096 KB |
Output is correct |
35 |
Correct |
323 ms |
37068 KB |
Output is correct |
36 |
Correct |
233 ms |
30136 KB |
Output is correct |
37 |
Correct |
307 ms |
47544 KB |
Output is correct |
38 |
Correct |
242 ms |
30252 KB |
Output is correct |
39 |
Correct |
304 ms |
35632 KB |
Output is correct |
40 |
Correct |
302 ms |
36100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
876 KB |
Output is correct |
2 |
Correct |
2 ms |
924 KB |
Output is correct |
3 |
Correct |
2 ms |
876 KB |
Output is correct |
4 |
Correct |
2 ms |
876 KB |
Output is correct |
5 |
Correct |
2 ms |
876 KB |
Output is correct |
6 |
Correct |
2 ms |
876 KB |
Output is correct |
7 |
Correct |
2 ms |
876 KB |
Output is correct |
8 |
Correct |
2 ms |
876 KB |
Output is correct |
9 |
Correct |
2 ms |
876 KB |
Output is correct |
10 |
Correct |
2 ms |
876 KB |
Output is correct |
11 |
Execution timed out |
2076 ms |
6688 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
876 KB |
Output is correct |
2 |
Correct |
2 ms |
924 KB |
Output is correct |
3 |
Correct |
2 ms |
876 KB |
Output is correct |
4 |
Correct |
2 ms |
876 KB |
Output is correct |
5 |
Correct |
2 ms |
876 KB |
Output is correct |
6 |
Correct |
2 ms |
876 KB |
Output is correct |
7 |
Correct |
2 ms |
876 KB |
Output is correct |
8 |
Correct |
2 ms |
876 KB |
Output is correct |
9 |
Correct |
2 ms |
876 KB |
Output is correct |
10 |
Correct |
2 ms |
876 KB |
Output is correct |
11 |
Correct |
250 ms |
28472 KB |
Output is correct |
12 |
Correct |
266 ms |
28088 KB |
Output is correct |
13 |
Correct |
271 ms |
27448 KB |
Output is correct |
14 |
Correct |
236 ms |
27576 KB |
Output is correct |
15 |
Correct |
246 ms |
28472 KB |
Output is correct |
16 |
Correct |
251 ms |
27704 KB |
Output is correct |
17 |
Correct |
250 ms |
27576 KB |
Output is correct |
18 |
Correct |
212 ms |
29496 KB |
Output is correct |
19 |
Correct |
208 ms |
26552 KB |
Output is correct |
20 |
Correct |
273 ms |
28148 KB |
Output is correct |
21 |
Correct |
309 ms |
40872 KB |
Output is correct |
22 |
Correct |
330 ms |
47924 KB |
Output is correct |
23 |
Correct |
303 ms |
35716 KB |
Output is correct |
24 |
Correct |
300 ms |
36144 KB |
Output is correct |
25 |
Correct |
316 ms |
42880 KB |
Output is correct |
26 |
Correct |
333 ms |
37124 KB |
Output is correct |
27 |
Correct |
321 ms |
36992 KB |
Output is correct |
28 |
Correct |
272 ms |
49924 KB |
Output is correct |
29 |
Correct |
250 ms |
30232 KB |
Output is correct |
30 |
Correct |
329 ms |
40284 KB |
Output is correct |
31 |
Correct |
318 ms |
39508 KB |
Output is correct |
32 |
Correct |
323 ms |
38276 KB |
Output is correct |
33 |
Correct |
282 ms |
42168 KB |
Output is correct |
34 |
Correct |
303 ms |
36096 KB |
Output is correct |
35 |
Correct |
323 ms |
37068 KB |
Output is correct |
36 |
Correct |
233 ms |
30136 KB |
Output is correct |
37 |
Correct |
307 ms |
47544 KB |
Output is correct |
38 |
Correct |
242 ms |
30252 KB |
Output is correct |
39 |
Correct |
304 ms |
35632 KB |
Output is correct |
40 |
Correct |
302 ms |
36100 KB |
Output is correct |
41 |
Execution timed out |
2076 ms |
6688 KB |
Time limit exceeded |
42 |
Halted |
0 ms |
0 KB |
- |