#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define all(x) begin(x), end(x)
const int MOD = 1e9+7;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int mx = 1000005;
int L, Q;
string S;
string T[mx];
// int three_pow[15];
// int three_sub[1594323];
// void smallL(){
// three_pow[0] = 1;
// for(int i = 1; i <= L; i++){
// three_pow[i] = three_pow[i-1]*3;
// }
// for(int i = 0; i < three_pow[L]; i++){
// int sub = i;
// int sum = 0;
// for(int j = 0; j < L; j++){
// if(sub % 3 == 2){
// //cout << i << " " << i-2*three_pow[j] << " " << i-1*three_pow[j] << "\n";
// three_sub[i] = three_sub[i-2*three_pow[j]]+three_sub[i-1*three_pow[j]];
// sum = -1;
// break;
// }
// if(sub % 3 == 1){
// sum+=(1<<j);
// }
// sub/=3;
// }
// if(sum != -1){
// three_sub[i] = S[sum]-'0';
// //cout << i << " " << three_sub[i] << "\n";
// }
// }
// //cout << "three_sub[2]: " << three_sub[8] << "\n";
// for(int i = 1; i <= Q; i++){
// int sub = 0;
// for(int j = 0; j < L; j++){
// if(T[i][j] == '1'){
// sub+=three_pow[j];
// }
// else if(T[i][j] == '?'){
// sub+=2*three_pow[j];
// }
// }
// cout << three_sub[sub] << "\n";
// }
// }
int trip[3][1<<20];
void genTrip(){
for(int i = 0; i < (1<<L); i++){
trip[2][i] = S[i]-'0';
}
for(int typ = 0; typ < 2; typ++){
array<int, 1<<20> dp;
array<int, 1<<20> ndp;
for(int i = 0; i < (1<<20); i++){
dp[i] = trip[2][i];
ndp[i] = 0;
}
for(int j = 0; j < L; j++){
for(int i = 0; i < (1<<L); i++){
if((i>>j)&1){ //put in ?
ndp[i] = dp[i-(1<<j)]+dp[i];
}
else{
if(typ == 1){
ndp[i] = dp[i];
}
else{
ndp[i] = dp[i+(1<<j)];
}
}
}
swap(dp, ndp);
for(int i = 0; i < (1<<L); i++){
ndp[i] = 0;
}
}
for(int i = 0; i < (1<<L); i++){
bool is_odd = 0;
for(int j = 0; j < L; j++){
if((i>>j)&1){
is_odd^=1;
}
}
if(is_odd){
trip[typ][i] = -dp[i];
}
else{
trip[typ][i] = dp[i];
}
}
}
}
void printTrip(){
map<char, int> from_char;
from_char['0'] = 0;
from_char['1'] = 1;
from_char['?'] = 2;
for(int i = 1; i <= Q; i++){
vi typ_count(3, 0);
for(auto u: T[i]){
typ_count[from_char[u]]++;
}
int typ = -1;
int min_typ_count = min(typ_count[0], min(typ_count[1], typ_count[2]));
for(int i = 0; i < 3; i++){
if(typ_count[i] == min_typ_count){
typ = i;
break;
}
}
// cout << "typ: " << typ << "\n";
// cout << trip[1][0] << "\n";
int sub1 = 0; //positions of typ
int sub2 = 0; //
for(int j = 0; j < L; j++){
int char_type = from_char[T[i][j]];
if(char_type == typ){
sub1+=(1<<j);
}
else{
if(typ == 2){
if(char_type == 1){
sub2+=(1<<j);
}
}
else{
if(char_type == 2){
sub2+=(1<<j);
}
}
}
}
int res = 0;
for(int i = sub1;;i = ((i-1)&sub1)){
res+=trip[typ][i+sub2];
// if(res >= MOD) res-=MOD;
// if(res < 0) res+=MOD;
if(i == 0) break;
}
if(typ != 2){
bool is_odd = 0;
for(auto u: T[i]){
if(from_char[u] == 2 || from_char[u] == typ){
is_odd^=1;
}
}
if(is_odd){
res = -res;
// if(res >= MOD) res-=MOD;
// if(res < 0) res+=MOD;
}
}
cout << res << "\n";
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> L >> Q;
cin >> S;
for(int i = 1; i <= Q; i++){
cin >> T[i];
reverse(all(T[i]));
}
// if(L <= 13){
// smallL();
// exit(0);
// }
genTrip();
printTrip();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
39876 KB |
Output is correct |
2 |
Correct |
50 ms |
39856 KB |
Output is correct |
3 |
Correct |
53 ms |
39944 KB |
Output is correct |
4 |
Correct |
52 ms |
39800 KB |
Output is correct |
5 |
Correct |
57 ms |
39756 KB |
Output is correct |
6 |
Correct |
51 ms |
39872 KB |
Output is correct |
7 |
Correct |
59 ms |
39836 KB |
Output is correct |
8 |
Correct |
52 ms |
39836 KB |
Output is correct |
9 |
Correct |
50 ms |
39792 KB |
Output is correct |
10 |
Correct |
50 ms |
39872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
39876 KB |
Output is correct |
2 |
Correct |
50 ms |
39856 KB |
Output is correct |
3 |
Correct |
53 ms |
39944 KB |
Output is correct |
4 |
Correct |
52 ms |
39800 KB |
Output is correct |
5 |
Correct |
57 ms |
39756 KB |
Output is correct |
6 |
Correct |
51 ms |
39872 KB |
Output is correct |
7 |
Correct |
59 ms |
39836 KB |
Output is correct |
8 |
Correct |
52 ms |
39836 KB |
Output is correct |
9 |
Correct |
50 ms |
39792 KB |
Output is correct |
10 |
Correct |
50 ms |
39872 KB |
Output is correct |
11 |
Correct |
571 ms |
44072 KB |
Output is correct |
12 |
Correct |
607 ms |
43812 KB |
Output is correct |
13 |
Correct |
607 ms |
42960 KB |
Output is correct |
14 |
Correct |
661 ms |
43160 KB |
Output is correct |
15 |
Correct |
686 ms |
44052 KB |
Output is correct |
16 |
Correct |
717 ms |
43480 KB |
Output is correct |
17 |
Correct |
690 ms |
43332 KB |
Output is correct |
18 |
Correct |
424 ms |
45160 KB |
Output is correct |
19 |
Correct |
475 ms |
42092 KB |
Output is correct |
20 |
Correct |
619 ms |
43716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
39876 KB |
Output is correct |
2 |
Correct |
50 ms |
39856 KB |
Output is correct |
3 |
Correct |
53 ms |
39944 KB |
Output is correct |
4 |
Correct |
52 ms |
39800 KB |
Output is correct |
5 |
Correct |
57 ms |
39756 KB |
Output is correct |
6 |
Correct |
51 ms |
39872 KB |
Output is correct |
7 |
Correct |
59 ms |
39836 KB |
Output is correct |
8 |
Correct |
52 ms |
39836 KB |
Output is correct |
9 |
Correct |
50 ms |
39792 KB |
Output is correct |
10 |
Correct |
50 ms |
39872 KB |
Output is correct |
11 |
Correct |
571 ms |
44072 KB |
Output is correct |
12 |
Correct |
607 ms |
43812 KB |
Output is correct |
13 |
Correct |
607 ms |
42960 KB |
Output is correct |
14 |
Correct |
661 ms |
43160 KB |
Output is correct |
15 |
Correct |
686 ms |
44052 KB |
Output is correct |
16 |
Correct |
717 ms |
43480 KB |
Output is correct |
17 |
Correct |
690 ms |
43332 KB |
Output is correct |
18 |
Correct |
424 ms |
45160 KB |
Output is correct |
19 |
Correct |
475 ms |
42092 KB |
Output is correct |
20 |
Correct |
619 ms |
43716 KB |
Output is correct |
21 |
Correct |
684 ms |
44412 KB |
Output is correct |
22 |
Correct |
753 ms |
44408 KB |
Output is correct |
23 |
Correct |
708 ms |
43332 KB |
Output is correct |
24 |
Correct |
820 ms |
43188 KB |
Output is correct |
25 |
Correct |
806 ms |
45296 KB |
Output is correct |
26 |
Correct |
828 ms |
43740 KB |
Output is correct |
27 |
Correct |
812 ms |
43688 KB |
Output is correct |
28 |
Correct |
494 ms |
46256 KB |
Output is correct |
29 |
Correct |
591 ms |
42172 KB |
Output is correct |
30 |
Correct |
686 ms |
44444 KB |
Output is correct |
31 |
Correct |
843 ms |
44272 KB |
Output is correct |
32 |
Correct |
836 ms |
44208 KB |
Output is correct |
33 |
Correct |
662 ms |
43076 KB |
Output is correct |
34 |
Correct |
818 ms |
43196 KB |
Output is correct |
35 |
Correct |
861 ms |
43716 KB |
Output is correct |
36 |
Correct |
451 ms |
42164 KB |
Output is correct |
37 |
Correct |
741 ms |
44228 KB |
Output is correct |
38 |
Correct |
570 ms |
42168 KB |
Output is correct |
39 |
Correct |
736 ms |
43416 KB |
Output is correct |
40 |
Correct |
812 ms |
43428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
39876 KB |
Output is correct |
2 |
Correct |
50 ms |
39856 KB |
Output is correct |
3 |
Correct |
53 ms |
39944 KB |
Output is correct |
4 |
Correct |
52 ms |
39800 KB |
Output is correct |
5 |
Correct |
57 ms |
39756 KB |
Output is correct |
6 |
Correct |
51 ms |
39872 KB |
Output is correct |
7 |
Correct |
59 ms |
39836 KB |
Output is correct |
8 |
Correct |
52 ms |
39836 KB |
Output is correct |
9 |
Correct |
50 ms |
39792 KB |
Output is correct |
10 |
Correct |
50 ms |
39872 KB |
Output is correct |
11 |
Correct |
269 ms |
55992 KB |
Output is correct |
12 |
Correct |
271 ms |
56568 KB |
Output is correct |
13 |
Correct |
251 ms |
56560 KB |
Output is correct |
14 |
Correct |
279 ms |
56484 KB |
Output is correct |
15 |
Correct |
261 ms |
56504 KB |
Output is correct |
16 |
Correct |
275 ms |
56520 KB |
Output is correct |
17 |
Correct |
266 ms |
56456 KB |
Output is correct |
18 |
Correct |
233 ms |
56716 KB |
Output is correct |
19 |
Correct |
250 ms |
56312 KB |
Output is correct |
20 |
Correct |
239 ms |
56492 KB |
Output is correct |
21 |
Correct |
295 ms |
56568 KB |
Output is correct |
22 |
Correct |
292 ms |
56508 KB |
Output is correct |
23 |
Correct |
244 ms |
56512 KB |
Output is correct |
24 |
Correct |
298 ms |
56448 KB |
Output is correct |
25 |
Correct |
279 ms |
56440 KB |
Output is correct |
26 |
Correct |
254 ms |
56304 KB |
Output is correct |
27 |
Correct |
275 ms |
56572 KB |
Output is correct |
28 |
Correct |
244 ms |
56320 KB |
Output is correct |
29 |
Correct |
269 ms |
56376 KB |
Output is correct |
30 |
Correct |
263 ms |
56428 KB |
Output is correct |
31 |
Correct |
258 ms |
56524 KB |
Output is correct |
32 |
Correct |
273 ms |
56444 KB |
Output is correct |
33 |
Correct |
288 ms |
56552 KB |
Output is correct |
34 |
Correct |
248 ms |
56364 KB |
Output is correct |
35 |
Correct |
268 ms |
56420 KB |
Output is correct |
36 |
Correct |
303 ms |
56568 KB |
Output is correct |
37 |
Correct |
288 ms |
56544 KB |
Output is correct |
38 |
Correct |
277 ms |
56576 KB |
Output is correct |
39 |
Correct |
273 ms |
56528 KB |
Output is correct |
40 |
Correct |
266 ms |
56444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
39876 KB |
Output is correct |
2 |
Correct |
50 ms |
39856 KB |
Output is correct |
3 |
Correct |
53 ms |
39944 KB |
Output is correct |
4 |
Correct |
52 ms |
39800 KB |
Output is correct |
5 |
Correct |
57 ms |
39756 KB |
Output is correct |
6 |
Correct |
51 ms |
39872 KB |
Output is correct |
7 |
Correct |
59 ms |
39836 KB |
Output is correct |
8 |
Correct |
52 ms |
39836 KB |
Output is correct |
9 |
Correct |
50 ms |
39792 KB |
Output is correct |
10 |
Correct |
50 ms |
39872 KB |
Output is correct |
11 |
Correct |
571 ms |
44072 KB |
Output is correct |
12 |
Correct |
607 ms |
43812 KB |
Output is correct |
13 |
Correct |
607 ms |
42960 KB |
Output is correct |
14 |
Correct |
661 ms |
43160 KB |
Output is correct |
15 |
Correct |
686 ms |
44052 KB |
Output is correct |
16 |
Correct |
717 ms |
43480 KB |
Output is correct |
17 |
Correct |
690 ms |
43332 KB |
Output is correct |
18 |
Correct |
424 ms |
45160 KB |
Output is correct |
19 |
Correct |
475 ms |
42092 KB |
Output is correct |
20 |
Correct |
619 ms |
43716 KB |
Output is correct |
21 |
Correct |
684 ms |
44412 KB |
Output is correct |
22 |
Correct |
753 ms |
44408 KB |
Output is correct |
23 |
Correct |
708 ms |
43332 KB |
Output is correct |
24 |
Correct |
820 ms |
43188 KB |
Output is correct |
25 |
Correct |
806 ms |
45296 KB |
Output is correct |
26 |
Correct |
828 ms |
43740 KB |
Output is correct |
27 |
Correct |
812 ms |
43688 KB |
Output is correct |
28 |
Correct |
494 ms |
46256 KB |
Output is correct |
29 |
Correct |
591 ms |
42172 KB |
Output is correct |
30 |
Correct |
686 ms |
44444 KB |
Output is correct |
31 |
Correct |
843 ms |
44272 KB |
Output is correct |
32 |
Correct |
836 ms |
44208 KB |
Output is correct |
33 |
Correct |
662 ms |
43076 KB |
Output is correct |
34 |
Correct |
818 ms |
43196 KB |
Output is correct |
35 |
Correct |
861 ms |
43716 KB |
Output is correct |
36 |
Correct |
451 ms |
42164 KB |
Output is correct |
37 |
Correct |
741 ms |
44228 KB |
Output is correct |
38 |
Correct |
570 ms |
42168 KB |
Output is correct |
39 |
Correct |
736 ms |
43416 KB |
Output is correct |
40 |
Correct |
812 ms |
43428 KB |
Output is correct |
41 |
Correct |
269 ms |
55992 KB |
Output is correct |
42 |
Correct |
271 ms |
56568 KB |
Output is correct |
43 |
Correct |
251 ms |
56560 KB |
Output is correct |
44 |
Correct |
279 ms |
56484 KB |
Output is correct |
45 |
Correct |
261 ms |
56504 KB |
Output is correct |
46 |
Correct |
275 ms |
56520 KB |
Output is correct |
47 |
Correct |
266 ms |
56456 KB |
Output is correct |
48 |
Correct |
233 ms |
56716 KB |
Output is correct |
49 |
Correct |
250 ms |
56312 KB |
Output is correct |
50 |
Correct |
239 ms |
56492 KB |
Output is correct |
51 |
Correct |
295 ms |
56568 KB |
Output is correct |
52 |
Correct |
292 ms |
56508 KB |
Output is correct |
53 |
Correct |
244 ms |
56512 KB |
Output is correct |
54 |
Correct |
298 ms |
56448 KB |
Output is correct |
55 |
Correct |
279 ms |
56440 KB |
Output is correct |
56 |
Correct |
254 ms |
56304 KB |
Output is correct |
57 |
Correct |
275 ms |
56572 KB |
Output is correct |
58 |
Correct |
244 ms |
56320 KB |
Output is correct |
59 |
Correct |
269 ms |
56376 KB |
Output is correct |
60 |
Correct |
263 ms |
56428 KB |
Output is correct |
61 |
Correct |
258 ms |
56524 KB |
Output is correct |
62 |
Correct |
273 ms |
56444 KB |
Output is correct |
63 |
Correct |
288 ms |
56552 KB |
Output is correct |
64 |
Correct |
248 ms |
56364 KB |
Output is correct |
65 |
Correct |
268 ms |
56420 KB |
Output is correct |
66 |
Correct |
303 ms |
56568 KB |
Output is correct |
67 |
Correct |
288 ms |
56544 KB |
Output is correct |
68 |
Correct |
277 ms |
56576 KB |
Output is correct |
69 |
Correct |
273 ms |
56528 KB |
Output is correct |
70 |
Correct |
266 ms |
56444 KB |
Output is correct |
71 |
Runtime error |
178 ms |
65540 KB |
Execution killed with signal 9 |
72 |
Halted |
0 ms |
0 KB |
- |