QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#290614 | #6237. 寻宝游戏 | MoRanSky | 100 ✓ | 260ms | 6548kb | C++23 | 2.3kb | 2023-12-25 06:06:17 | 2023-12-25 06:06:17 |
Judging History
answer
// Skyqwq
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N = 1005, M = 5005, P = 1e9 + 7;
int n, m, q, f[N], g[N], pw[N];
// f È« 1£» g È« 0
bitset<M> a[N], r[N], st, fl, bk[N], qz;
char s[M];
void inline add(int &x, int y) {
x += y;
if (x >= P) x -= P;
}
int ask(int n) {
if (fl.none()) return pw[n];
if (!n) {
if (st.count()) return 0;
return 1;
}
if (st.count() == 0) {
if ((a[n] & fl).none()) {
return (pw[n - 1] + ask(n - 1)) % P;
} else {
fl &= a[n];
st &= a[n];
return ask(n - 1);
}
} else if (st == fl) {
if ((~a[n] & fl).none()) {
return (pw[n - 1] + ask(n - 1)) % P;
} else {
fl &= (~a[n]);
st &= (~a[n]);
return ask(n - 1);
}
} else {
if (st == (fl & a[n])) {
int ret = 0;
bk[n] = fl ^ st;
fl = st;
add(ret, ask(n - 1));
fl = bk[n];
st.reset();
add(ret, ask(n - 1));
return ret;
} else if (((a[n] & fl) & st) == (a[n] & fl)) {
fl &= (~a[n]);
st &= (~a[n]);
return ask(n - 1);
} else if ((st & (~a[n])).none()) {
fl &= a[n];
st &= a[n];
return ask(n - 1);
}
}
return 0;
}
int ans[N];
int main() {
pw[0] = 1;
read(n), read(m), read(q);
for (int i = 1; i <= n; i++) {
pw[i] = pw[i - 1] * 2 % P;
scanf("%s", s + 1);
for (int j = 1; j <= m; j++)
if (s[j] == '1') a[i][j] = 1;
}
for (int i = 1; i <= q; i++) {
scanf("%s", s + 1);
for (int j = 1; j <= m; j++)
if (s[j] == '1') r[i][j] = 1;
}
for (int i = 1; i <= q; i++) {
if (i > 1 && r[i] == r[i - 1]) {
printf("%d\n", ans[i] = ans[i - 1]);
continue;
}
st = r[i];
fl.reset();
for (int j = 1; j <= m; j++) fl[j] = 1;
printf("%d\n", ans[i] = ask(n));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 0ms
memory: 3884kb
input:
20 30 1 010100001010100101010101010111 001111111001111100010111111000 011100111101000011111111111001 010110010011100010110110000111 001001100010011111000001101011 000011101011011010100101110011 001100000111001110100101101110 000101111001100111010111110101 000000111010010011010110110011 1001111000111...
output:
1669
result:
ok 1 number(s): "1669"
Test #2:
score: 10
Accepted
time: 173ms
memory: 6284kb
input:
1000 16 1000 0011100011111111 0011011010111010 0110011110110011 1010011111000011 1001011001100111 1111001101000010 0001000110101101 1100000111101010 1011100111111111 1110100010110001 0111010001101010 0001111111011101 0010111001111111 0000000100010011 0011100111010000 1110110111001001 110100000000100...
output:
546311852 68821743 862357315 435679482 167927461 455884328 455884328 435679482 329191893 68821743 0 455884328 453074185 455884328 435679482 12465940 956544033 210043177 546311852 546311852 546311852 0 167927461 862357315 700228207 329191893 68821743 329191893 329191893 12465940 956544033 700228207 9...
result:
ok 1000 numbers
Test #3:
score: 10
Accepted
time: 177ms
memory: 6120kb
input:
1000 16 1000 0101100010010000 1000111011001101 1101001111111010 1110101100010001 0101100000000101 1010011110111111 0111111110011010 0010110101111100 1010100000111110 1000110000011010 1110010100011111 0001000111110111 1010011110110100 1100010011000100 1111110111100011 0111011101100111 100011111111101...
output:
600117192 628057030 520500655 152386859 0 949829617 949829617 949829617 651886608 0 767563562 567224118 51663599 567224118 504514244 655570883 628057030 653311634 651886608 600117192 655570883 762981745 651886608 0 0 655570883 767563562 520500655 628057030 0 762981745 628057030 655570883 520500655 6...
result:
ok 1000 numbers
Test #4:
score: 10
Accepted
time: 105ms
memory: 5480kb
input:
500 1000 1000 0011010011000100101111101101101101011100000001011001010101111101011100101111100001100000101101010101100100011001011111110011101110010111111100100000001111111100000110000110101010001101000101010000010100111101111011010110101101000110000111010011011001111000100001011010100100011000110110...
output:
714663864 209138641 606477942 0 958723037 691619641 859772532 285889785 537262220 461859766 86481620 0 605081682 62403003 739399055 615880199 111913839 0 641761956 86481620 494137212 587867528 901066820 495226355 700215543 318838879 397386814 795789207 0 0 756057791 452676554 728623746 557436488 244...
result:
ok 1000 numbers
Test #5:
score: 10
Accepted
time: 95ms
memory: 5404kb
input:
500 1000 1000 0001001101001100001110001100001010101111101011011011011100101001010101001111101111100101110011011010111010110100101010111100101110011101000100010000001111111010101110011001011111011110111111100011001010111100101110101101000100110011100101101101010011101111010001000111101111000111000110...
output:
441872489 208921884 203810130 457905314 45281445 459958033 433045769 690543053 73984238 887079939 334794090 0 662961762 0 0 141891093 794074520 111432275 274034870 750374820 693541831 737491733 262585116 180251071 764661580 31792038 570316499 613306508 0 435458357 997008963 903351888 559377819 0 187...
result:
ok 1000 numbers
Test #6:
score: 10
Accepted
time: 101ms
memory: 5504kb
input:
500 1000 1000 0000011100101100010011000011111000111000011010110101100110100011100010000111101100111110110101101110000001101110100101110000011101011000011000110001010110011100101100010100001000011100101100001101110111111100110101000010001110110001011011110110101110101001011111000111000101010010101001...
output:
654245907 294743637 782762565 790835260 0 83164394 502425569 778577661 7867265 625419989 690855182 0 446490678 0 636056215 0 212077492 0 327046796 577348769 482780640 419901865 0 137566488 0 0 962941788 208480332 657297348 920407413 254837290 784077505 0 0 965616959 91005509 251915364 849900033 0 19...
result:
ok 1000 numbers
Test #7:
score: 10
Accepted
time: 107ms
memory: 5492kb
input:
500 1000 1000 0001000110010010011110101001100111101101001010111110101100011110101111010110101000011010100011101101001111100111111000001101011011000110111010110001010000011001100000001011101111111100100111110110101101110101010000011001100110100101101000010000100110111110100000011011000101000101110001...
output:
539317615 286248539 369652647 425325986 397273375 99895194 861779773 0 466122875 943841819 0 767498253 688213683 548559332 967417819 427469802 661679983 170736998 82613009 624971048 172687009 704182737 164405700 856796890 980124190 640011751 524898836 0 502803994 524898836 0 44883507 968928673 71251...
result:
ok 1000 numbers
Test #8:
score: 10
Accepted
time: 260ms
memory: 6464kb
input:
1000 5000 1000 000011110101110100111100100001100001011110100101010000111011110001000101110101100010011000101000100111100101000001100010000100110101110110001111011000001001110000001001000110001001011000111101010011010011100110010001110011110101010001111000001101111100100100001000111100010010000011000...
output:
621147360 931440739 363611112 0 583003560 308763159 707862232 779837890 461161807 897798304 684355400 0 4170902 981889724 0 10107617 153926106 265071337 0 379316227 258858045 6947079 815617695 134667641 289307899 891277029 518548887 338755257 846676827 78941050 456427349 104211396 908622168 26100453...
result:
ok 1000 numbers
Test #9:
score: 10
Accepted
time: 258ms
memory: 6548kb
input:
1000 5000 1000 111111011011101011011100000000010111011000011000011101001101000001111001111101000010101010110010111001111110010001101011010101001001011110110000000001000110100001001100100100000011101110000110011000010000101110000100000101111001111110101000100011000100000110110010000010010111000101110...
output:
400451441 207463336 443021276 303513108 317633292 668164093 0 551069870 820095280 324065518 215153567 0 845657910 336592801 33660198 616685304 974122807 238491686 0 712032641 170037184 259414032 755661998 37270378 405633065 690243906 818119594 357789876 229014319 633381959 263484114 765058189 505486...
result:
ok 1000 numbers
Test #10:
score: 10
Accepted
time: 251ms
memory: 6476kb
input:
1000 5000 1000 001001001011101000010000010000111110001110100101100110101010010000000110010100101101000000001010110110010001000110110001000001001110010100110010101000000111101001011100111100011111001010101011010000011011010111011100110111110010110110100110000101101101000011100101000110011000100010101...
output:
349645569 682232555 131502487 925844186 729216670 56429626 0 0 841372429 0 0 48642371 452626412 133952726 882044283 914905873 8172328 698935486 194048997 0 390582741 0 697142283 56434125 504704923 741770747 13149033 722604458 713443367 0 41482463 104841061 693630856 265842014 879030090 255237097 0 2...
result:
ok 1000 numbers