QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#356848 | #1286. Ternary String Counting | james1BadCreeper | TL | 247ms | 101652kb | C++14 | 2.0kb | 2024-03-18 13:51:47 | 2024-03-18 13:51:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
const int P = 1e9 + 7;
inline void add(int &x, int k) { x = (x + k) % P; }
inline void sub(int &x, int k) { x = (x - k + P) % P; }
int n, m;
int mnj[N], mxj[N], mnk[N], mxk[N], f[N][N];
int rs[N], cs[N], tmp[N], lk[N], rk[N];
inline void del(int j, int k) {
sub(rs[j], f[j][k]); sub(cs[k], f[j][k]);
f[j][k] = 0;
}
void solve(void) {
cin >> n >> m;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) f[i][j] = 0;
mnj[i] = mnk[i] = 0, mxj[i] = mxk[i] = n;
rs[i] = cs[i] = 0; lk[i] = 0; rk[i] = n;
}
while (m--) {
int l, r, x; cin >> l >> r >> x;
if (x == 1) mxj[r] = min(mxj[r], l - 1);
else if (x == 2) mnj[r] = max(mnj[r], l), mxk[r] = min(mxk[r], l - 1);
else mnk[r] = max(mnk[r], l);
}
f[0][0] = rs[0] = cs[0] = 1;
int lj = 0;
for (int i = 1; i <= n; ++i) {
if (mnj[i] <= i - 1 && i - 1 <= mxj[i]) {
for (int k = 0; k < i; ++k) tmp[k] = (rs[k] + cs[k]) % P;
for (int k = mnk[i]; k <= min(mxk[i], max(0, i - 2)); ++k) // f[i][i - 1][k]
add(f[i - 1][k], tmp[k]),
add(rs[i - 1], tmp[k]),
add(cs[k], tmp[k]);
}
for (int j = lj; j < i; ++j)
if (j < mnj[i] || j > mxj[i]) {
for (int k = 0; k <= n; ++k) del(j, k);
lk[j] = n; rk[j] = 0;
} else {
for (int k = lk[j]; k < mnk[i]; ++k) del(j, k);
for (int k = mxk[i] + 1; k <= rk[j]; ++k) del(j, k);
lk[j] = max(lk[j], mnk[i]);
rk[j] = min(rk[j], mxk[i]);
}
}
int ans = 0;
for (int i = 0; i <= n; ++i) add(ans, rs[i]);
cout << ans << '\n';
}
int main(void) {
ios::sync_with_stdio(0);
int T; cin >> T;
while (T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3716kb
input:
4 1 0 2 0 3 0 5 2 1 3 3 4 5 1
output:
3 9 27 18
result:
ok 4 tokens
Test #2:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
741 5 3 1 5 3 3 4 2 1 4 3 4 3 2 4 2 1 4 1 2 3 3 10 3 9 10 2 3 6 3 1 9 1 3 4 2 3 2 1 3 2 2 3 3 1 3 3 10 4 6 6 1 9 10 2 4 8 3 4 10 3 6 3 1 4 3 2 4 2 2 2 2 4 3 1 4 1 1 1 2 2 3 1 5 3 4 5 2 4 5 1 1 4 3 9 3 2 3 2 1 9 2 2 4 2 4 3 1 3 3 2 3 2 1 2 3 8 4 5 8 1 4 8 1 3 5 3 1 3 3 9 3 4 5 1 1 5 3 3 8 2 8 3 5 7 2...
output:
90 0 0 0 24300 0 0 0 768 0 0 972 2916 0 6480 864 0 0 0 0 0 0 0 0 6 0 0 0 0 0 96 0 6 0 0 0 0 0 0 0 108 0 0 0 2916 0 0 0 0 0 0 0 0 0 0 324 8748 0 0 0 0 0 0 4320 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0 1992 0 0 450 0 162 1656 0 0 0 0 0 54 0 18 0 0 0 0 744 0 1620 324 0 0 36 36 0 0 60 6 54 0 0 0 0 0 0 0 0 243 810...
result:
ok 741 tokens
Test #3:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
332 17 5 4 9 1 4 6 1 7 17 1 5 5 1 5 6 3 13 5 10 12 3 8 13 2 1 10 3 2 9 1 9 10 1 19 5 11 13 1 9 17 2 1 7 1 4 4 2 3 9 1 15 4 8 11 2 9 14 3 10 12 2 4 5 2 12 4 3 9 2 7 8 1 1 7 3 6 7 3 16 5 4 14 3 1 5 1 2 10 1 2 12 3 6 9 3 20 4 10 17 3 4 20 3 17 19 3 8 17 1 20 5 11 11 1 9 13 1 1 5 3 17 17 3 3 18 3 17 5 1...
output:
0 0 0 2047032 0 0 0 0 0 839808 0 0 0 0 0 0 0 0 0 0 0 0 44641044 0 20412 0 0 0 0 0 0 0 6 0 0 0 0 81 0 0 0 0 0 0 0 0 0 0 0 313155072 0 0 0 0 0 0 0 0 0 5400 0 10368 0 0 0 0 14580 0 0 0 217728 40310784 0 0 218700 0 0 0 0 1620 0 0 0 0 0 108 146304 0 0 0 466560 288 0 0 0 0 0 0 0 276138 0 0 0 0 0 0 0 52488...
result:
ok 332 tokens
Test #4:
score: 0
Accepted
time: 51ms
memory: 24484kb
input:
5 1000 0 1000 5 779 779 2 543 840 3 30 477 1 10 295 3 463 741 1 1000 6 379 569 1 249 826 2 194 819 3 90 400 1 614 808 2 102 868 2 1000 8 463 981 1 680 857 3 560 623 1 209 659 1 55 957 2 244 327 1 321 888 3 37 204 3 1000 5 336 851 3 410 676 1 522 911 2 165 962 1 258 330 3
output:
56888193 0 0 0 0
result:
ok 5 tokens
Test #5:
score: 0
Accepted
time: 46ms
memory: 24212kb
input:
5 1000 9 190 765 1 212 745 3 437 798 3 682 814 3 122 289 1 44 821 1 115 448 3 400 936 2 562 639 3 1000 5 561 808 3 23 160 2 57 915 2 211 943 3 125 596 2 1000 1 398 739 2 1000 3 629 973 2 7 721 2 591 815 2 1000 10 536 708 1 217 256 2 690 913 3 418 871 2 302 325 2 334 830 2 496 573 2 396 865 1 240 837...
output:
0 0 722271060 85306976 0
result:
ok 5 tokens
Test #6:
score: 0
Accepted
time: 57ms
memory: 42952kb
input:
2 2000 1 1501 1703 2 2000 5 1230 1521 3 1022 1939 3 1241 1283 3 767 1944 2 303 1163 3
output:
841960641 0
result:
ok 2 tokens
Test #7:
score: 0
Accepted
time: 61ms
memory: 43596kb
input:
2 2000 2 640 1942 1 1473 1917 3 2000 4 490 887 1 670 1163 3 824 1434 2 1221 1746 1
output:
0 0
result:
ok 2 tokens
Test #8:
score: 0
Accepted
time: 247ms
memory: 101580kb
input:
1 5000 9 2821 3377 2 798 1535 2 3563 4161 3 2205 2946 3 1320 1594 3 278 1624 1 1243 2759 3 2882 4939 1 2639 3559 3
output:
0
result:
ok "0"
Test #9:
score: 0
Accepted
time: 200ms
memory: 101636kb
input:
1 5000 2 539 4252 1 906 3821 1
output:
101862333
result:
ok "101862333"
Test #10:
score: 0
Accepted
time: 0ms
memory: 5896kb
input:
111 34 0 30 0 18 0 35 0 3 0 43 0 13 0 28 0 57 0 75 0 31 0 4 0 92 0 1 0 53 0 85 0 74 0 43 0 59 0 72 0 79 0 40 0 70 0 36 0 86 0 56 0 53 0 66 0 50 0 100 0 60 0 74 0 50 0 51 0 92 0 49 0 50 0 78 0 95 0 4 0 59 0 44 0 92 0 84 0 7 0 75 0 99 0 56 0 54 0 13 0 27 0 33 0 22 0 80 0 14 0 79 0 29 0 39 0 21 0 97 0 ...
output:
582926302 130653412 387420489 748778899 27 738321955 1594323 792294829 998064805 100094381 391960236 81 587240675 3 172815616 473062299 700031465 738321955 982583189 966670169 107644805 953271190 662963356 246336683 419186890 666021604 172815616 909419307 710104287 886041711 947749553 700031465 7101...
result:
ok 111 tokens
Test #11:
score: 0
Accepted
time: 4ms
memory: 12404kb
input:
16 350 0 453 0 485 0 361 0 498 0 149 0 433 0 435 0 279 0 240 0 166 0 152 0 393 0 159 0 219 0 222 0
output:
378029361 68761795 621961191 766744305 24977444 679213660 705815658 352340880 186665231 458529104 150230246 338768694 907169137 887128598 322586612 709838468
result:
ok 16 tokens
Test #12:
score: 0
Accepted
time: 84ms
memory: 101652kb
input:
1 5000 0
output:
22443616
result:
ok "22443616"
Test #13:
score: -100
Time Limit Exceeded
input:
1 5000 1000000 4736 4854 3 405 1465 3 835 4720 3 633 1954 3 2182 4257 3 1920 3098 3 302 3157 3 63 3964 3 4032 4116 3 734 1980 3 1083 4515 3 44 4768 3 20 4466 3 1160 2774 3 794 1531 3 2301 4714 3 255 4939 3 2699 2967 3 1835 2733 3 582 2071 3 430 1857 3 249 2013 3 922 4833 3 13 1973 3 3150 3812 3 2904...