#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[(1<<12)];
ll get3(ll val,ll ip){
return (val/po[ip])%3;
}
void cal(ll id){
REP(i,po[k]){
ll tx=0,ck=1;
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]];
ck=0;
break;
}
tx=tx*2+get3(i,k-j-1);
}
if(ck)dp[i]=s[(id<<k)+tx]-'0';
}
}
void DFS(ll id,ll le,ll qid,ll tx){
if(id==l-k){que[le].pb(mp(tx,qid));return ;}
if(a[id]=='?'){
DFS(id+1,(le<<1)+1,qid,tx);
DFS(id+1,(le<<1),qid,tx);
return;
}
if(a[id]=='0')DFS(id+1,(le<<1),qid,tx);
if(a[id]=='1')DFS(id+1,(le<<1)+1,qid,tx);
return;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>l>>q;
cin>>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');
DFS(0,0,T,tx);
}
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1016 KB |
Output is correct |
2 |
Correct |
3 ms |
1004 KB |
Output is correct |
3 |
Correct |
2 ms |
1004 KB |
Output is correct |
4 |
Correct |
2 ms |
1004 KB |
Output is correct |
5 |
Correct |
3 ms |
1004 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 KB |
Output is correct |
7 |
Correct |
2 ms |
1004 KB |
Output is correct |
8 |
Correct |
2 ms |
1004 KB |
Output is correct |
9 |
Correct |
2 ms |
1004 KB |
Output is correct |
10 |
Correct |
2 ms |
1004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1016 KB |
Output is correct |
2 |
Correct |
3 ms |
1004 KB |
Output is correct |
3 |
Correct |
2 ms |
1004 KB |
Output is correct |
4 |
Correct |
2 ms |
1004 KB |
Output is correct |
5 |
Correct |
3 ms |
1004 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 KB |
Output is correct |
7 |
Correct |
2 ms |
1004 KB |
Output is correct |
8 |
Correct |
2 ms |
1004 KB |
Output is correct |
9 |
Correct |
2 ms |
1004 KB |
Output is correct |
10 |
Correct |
2 ms |
1004 KB |
Output is correct |
11 |
Correct |
250 ms |
29072 KB |
Output is correct |
12 |
Correct |
267 ms |
28600 KB |
Output is correct |
13 |
Correct |
251 ms |
27832 KB |
Output is correct |
14 |
Correct |
237 ms |
28088 KB |
Output is correct |
15 |
Correct |
248 ms |
28856 KB |
Output is correct |
16 |
Correct |
274 ms |
28088 KB |
Output is correct |
17 |
Correct |
249 ms |
28104 KB |
Output is correct |
18 |
Correct |
219 ms |
29880 KB |
Output is correct |
19 |
Correct |
213 ms |
26956 KB |
Output is correct |
20 |
Correct |
274 ms |
28636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1016 KB |
Output is correct |
2 |
Correct |
3 ms |
1004 KB |
Output is correct |
3 |
Correct |
2 ms |
1004 KB |
Output is correct |
4 |
Correct |
2 ms |
1004 KB |
Output is correct |
5 |
Correct |
3 ms |
1004 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 KB |
Output is correct |
7 |
Correct |
2 ms |
1004 KB |
Output is correct |
8 |
Correct |
2 ms |
1004 KB |
Output is correct |
9 |
Correct |
2 ms |
1004 KB |
Output is correct |
10 |
Correct |
2 ms |
1004 KB |
Output is correct |
11 |
Correct |
250 ms |
29072 KB |
Output is correct |
12 |
Correct |
267 ms |
28600 KB |
Output is correct |
13 |
Correct |
251 ms |
27832 KB |
Output is correct |
14 |
Correct |
237 ms |
28088 KB |
Output is correct |
15 |
Correct |
248 ms |
28856 KB |
Output is correct |
16 |
Correct |
274 ms |
28088 KB |
Output is correct |
17 |
Correct |
249 ms |
28104 KB |
Output is correct |
18 |
Correct |
219 ms |
29880 KB |
Output is correct |
19 |
Correct |
213 ms |
26956 KB |
Output is correct |
20 |
Correct |
274 ms |
28636 KB |
Output is correct |
21 |
Correct |
313 ms |
41020 KB |
Output is correct |
22 |
Correct |
339 ms |
48052 KB |
Output is correct |
23 |
Correct |
303 ms |
35972 KB |
Output is correct |
24 |
Correct |
298 ms |
36508 KB |
Output is correct |
25 |
Correct |
314 ms |
43392 KB |
Output is correct |
26 |
Correct |
325 ms |
37636 KB |
Output is correct |
27 |
Correct |
333 ms |
37304 KB |
Output is correct |
28 |
Correct |
276 ms |
50308 KB |
Output is correct |
29 |
Correct |
249 ms |
30616 KB |
Output is correct |
30 |
Correct |
328 ms |
40476 KB |
Output is correct |
31 |
Correct |
318 ms |
39944 KB |
Output is correct |
32 |
Correct |
323 ms |
38532 KB |
Output is correct |
33 |
Correct |
281 ms |
42424 KB |
Output is correct |
34 |
Correct |
319 ms |
36568 KB |
Output is correct |
35 |
Correct |
319 ms |
37248 KB |
Output is correct |
36 |
Correct |
231 ms |
30832 KB |
Output is correct |
37 |
Correct |
310 ms |
47812 KB |
Output is correct |
38 |
Correct |
242 ms |
30636 KB |
Output is correct |
39 |
Correct |
304 ms |
36100 KB |
Output is correct |
40 |
Correct |
300 ms |
36484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1016 KB |
Output is correct |
2 |
Correct |
3 ms |
1004 KB |
Output is correct |
3 |
Correct |
2 ms |
1004 KB |
Output is correct |
4 |
Correct |
2 ms |
1004 KB |
Output is correct |
5 |
Correct |
3 ms |
1004 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 KB |
Output is correct |
7 |
Correct |
2 ms |
1004 KB |
Output is correct |
8 |
Correct |
2 ms |
1004 KB |
Output is correct |
9 |
Correct |
2 ms |
1004 KB |
Output is correct |
10 |
Correct |
2 ms |
1004 KB |
Output is correct |
11 |
Execution timed out |
2073 ms |
28684 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1016 KB |
Output is correct |
2 |
Correct |
3 ms |
1004 KB |
Output is correct |
3 |
Correct |
2 ms |
1004 KB |
Output is correct |
4 |
Correct |
2 ms |
1004 KB |
Output is correct |
5 |
Correct |
3 ms |
1004 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 KB |
Output is correct |
7 |
Correct |
2 ms |
1004 KB |
Output is correct |
8 |
Correct |
2 ms |
1004 KB |
Output is correct |
9 |
Correct |
2 ms |
1004 KB |
Output is correct |
10 |
Correct |
2 ms |
1004 KB |
Output is correct |
11 |
Correct |
250 ms |
29072 KB |
Output is correct |
12 |
Correct |
267 ms |
28600 KB |
Output is correct |
13 |
Correct |
251 ms |
27832 KB |
Output is correct |
14 |
Correct |
237 ms |
28088 KB |
Output is correct |
15 |
Correct |
248 ms |
28856 KB |
Output is correct |
16 |
Correct |
274 ms |
28088 KB |
Output is correct |
17 |
Correct |
249 ms |
28104 KB |
Output is correct |
18 |
Correct |
219 ms |
29880 KB |
Output is correct |
19 |
Correct |
213 ms |
26956 KB |
Output is correct |
20 |
Correct |
274 ms |
28636 KB |
Output is correct |
21 |
Correct |
313 ms |
41020 KB |
Output is correct |
22 |
Correct |
339 ms |
48052 KB |
Output is correct |
23 |
Correct |
303 ms |
35972 KB |
Output is correct |
24 |
Correct |
298 ms |
36508 KB |
Output is correct |
25 |
Correct |
314 ms |
43392 KB |
Output is correct |
26 |
Correct |
325 ms |
37636 KB |
Output is correct |
27 |
Correct |
333 ms |
37304 KB |
Output is correct |
28 |
Correct |
276 ms |
50308 KB |
Output is correct |
29 |
Correct |
249 ms |
30616 KB |
Output is correct |
30 |
Correct |
328 ms |
40476 KB |
Output is correct |
31 |
Correct |
318 ms |
39944 KB |
Output is correct |
32 |
Correct |
323 ms |
38532 KB |
Output is correct |
33 |
Correct |
281 ms |
42424 KB |
Output is correct |
34 |
Correct |
319 ms |
36568 KB |
Output is correct |
35 |
Correct |
319 ms |
37248 KB |
Output is correct |
36 |
Correct |
231 ms |
30832 KB |
Output is correct |
37 |
Correct |
310 ms |
47812 KB |
Output is correct |
38 |
Correct |
242 ms |
30636 KB |
Output is correct |
39 |
Correct |
304 ms |
36100 KB |
Output is correct |
40 |
Correct |
300 ms |
36484 KB |
Output is correct |
41 |
Execution timed out |
2073 ms |
28684 KB |
Time limit exceeded |
42 |
Halted |
0 ms |
0 KB |
- |