#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';
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>l>>q;
cin>>s;
k=min(l,10LL);
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')!=(1&(i>>(l-k-i-1)))){ck=0;break;}
}
if(ck){
que[i].pb(mp(tx,T));
}
}
}
REP(i,(1<<(l-k))){
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 |
1004 KB |
Output is correct |
2 |
Correct |
2 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 |
2 ms |
1004 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 KB |
Output is correct |
7 |
Correct |
3 ms |
1004 KB |
Output is correct |
8 |
Correct |
3 ms |
1004 KB |
Output is correct |
9 |
Correct |
2 ms |
1004 KB |
Output is correct |
10 |
Correct |
2 ms |
1004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1004 KB |
Output is correct |
2 |
Correct |
2 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 |
2 ms |
1004 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 KB |
Output is correct |
7 |
Correct |
3 ms |
1004 KB |
Output is correct |
8 |
Correct |
3 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 |
247 ms |
28656 KB |
Output is correct |
12 |
Correct |
263 ms |
28336 KB |
Output is correct |
13 |
Correct |
240 ms |
27448 KB |
Output is correct |
14 |
Correct |
252 ms |
27576 KB |
Output is correct |
15 |
Correct |
246 ms |
28728 KB |
Output is correct |
16 |
Correct |
268 ms |
27704 KB |
Output is correct |
17 |
Correct |
252 ms |
27856 KB |
Output is correct |
18 |
Correct |
215 ms |
29624 KB |
Output is correct |
19 |
Correct |
211 ms |
26552 KB |
Output is correct |
20 |
Correct |
271 ms |
28572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1004 KB |
Output is correct |
2 |
Correct |
2 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 |
2 ms |
1004 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 KB |
Output is correct |
7 |
Correct |
3 ms |
1004 KB |
Output is correct |
8 |
Correct |
3 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 |
247 ms |
28656 KB |
Output is correct |
12 |
Correct |
263 ms |
28336 KB |
Output is correct |
13 |
Correct |
240 ms |
27448 KB |
Output is correct |
14 |
Correct |
252 ms |
27576 KB |
Output is correct |
15 |
Correct |
246 ms |
28728 KB |
Output is correct |
16 |
Correct |
268 ms |
27704 KB |
Output is correct |
17 |
Correct |
252 ms |
27856 KB |
Output is correct |
18 |
Correct |
215 ms |
29624 KB |
Output is correct |
19 |
Correct |
211 ms |
26552 KB |
Output is correct |
20 |
Correct |
271 ms |
28572 KB |
Output is correct |
21 |
Incorrect |
299 ms |
26492 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1004 KB |
Output is correct |
2 |
Correct |
2 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 |
2 ms |
1004 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 KB |
Output is correct |
7 |
Correct |
3 ms |
1004 KB |
Output is correct |
8 |
Correct |
3 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 |
Incorrect |
1348 ms |
62604 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1004 KB |
Output is correct |
2 |
Correct |
2 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 |
2 ms |
1004 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 KB |
Output is correct |
7 |
Correct |
3 ms |
1004 KB |
Output is correct |
8 |
Correct |
3 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 |
247 ms |
28656 KB |
Output is correct |
12 |
Correct |
263 ms |
28336 KB |
Output is correct |
13 |
Correct |
240 ms |
27448 KB |
Output is correct |
14 |
Correct |
252 ms |
27576 KB |
Output is correct |
15 |
Correct |
246 ms |
28728 KB |
Output is correct |
16 |
Correct |
268 ms |
27704 KB |
Output is correct |
17 |
Correct |
252 ms |
27856 KB |
Output is correct |
18 |
Correct |
215 ms |
29624 KB |
Output is correct |
19 |
Correct |
211 ms |
26552 KB |
Output is correct |
20 |
Correct |
271 ms |
28572 KB |
Output is correct |
21 |
Incorrect |
299 ms |
26492 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |