QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402871 | #1286. Ternary String Counting | Eray | ML | 145ms | 62844kb | C++14 | 2.7kb | 2024-05-01 17:03:14 | 2024-05-01 17:03:14 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long LL;
const int N = 5000 + 5;
const int M = 1e6 + 5;
const LL MOD = 1e9 + 7;
int n, m;
int jl[N], jr[N], kl[N], kr[N];
std::deque<int> non_zero[N];
LL f[N][N], sumr[N], sumc[N];
int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) jl[i] = 0, jr[i] = i - 1, kl[i] = 0, kr[i] = std::max(i - 2, 0);
for(int i = 1; i <= m; i++) {
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
if(x == 1) jr[r] = std::min(jr[r], l - 1), kr[r] = std::min(kr[r], std::max(l - 2, 0));
else if(x == 2) jl[r] = std::max(jl[r], l), kr[r] = std::min(kr[r], l - 1);
else if(x == 3) kl[r] = std::max(kl[r], l);
}
bool flag = true;
for(int i = 1; i <= n; i++) if(jl[i] > jr[i] || kl[i] > kr[i]) { puts("0"); flag = false; break; }
if(!flag) continue;
for(int j = 0; j <= n; j++) for(int k = 0; k <= n; k++) f[j][k] = 0;
for(int i = 0; i <= n; i++) sumr[i] = sumc[i] = 0;
for(int i = 0; i <= n; i++) {
non_zero[i].clear();
for(int j = 0; j <= n; j++) non_zero[i].emplace_back(j);
}
f[0][0] = 1, sumr[0] = sumc[0] = 1;
auto reset = [&](int i, int j) { (sumr[i] += MOD - f[i][j]) %= MOD, (sumc[j] += MOD - f[i][j]) %= MOD, f[i][j] = 0; };
for(int i = 1; i <= n; i++) {
// f[i - 1][j][k] -> f[i][i - 1][k]
for(int k = 0; k <= i - 3; k++) {
LL val = (sumc[k] - (k == 0 ? f[0][0] : 0LL) + MOD) % MOD;
(f[i - 1][k] += val) %= MOD, (sumr[i - 1] += val) %= MOD, (sumc[k] += val) %= MOD;
}
// f[i - 1][j][k] -> f[i][i - 1][j]
for(int j = 0; j <= i - 2; j++) {
LL val = sumr[j];
(f[i - 1][j] += val) %= MOD, (sumr[i - 1] += val) %= MOD, (sumc[j] += val) %= MOD;
}
// remain (jl[i]..jr[i], kl[i]..kr[i])
for(int j = 0; j < jl[i]; j++) {
for(int k : non_zero[j]) reset(j, k);
non_zero[j].clear();
}
for(int j = jr[i] + 1; j <= i - 1; j++) {
for(int k : non_zero[j]) reset(j, k);
non_zero[j].clear();
}
for(int j = jl[i]; j <= jr[i]; j++) {
while(!non_zero[j].empty() && non_zero[j].front() < kl[i]) reset(j, non_zero[j].front()), non_zero[j].pop_front();
while(!non_zero[j].empty() && non_zero[j].back() > kr[i]) reset(j, non_zero[j].back()), non_zero[j].pop_back();
}
// printf("i = %d: j[%d, %d], k[%d, %d]\n", i, jl[i], jr[i], kl[i], kr[i]);
// for(int j = 0; j < i; j++) for(int k = 0; k < std::max(j, 1); k++)
// if(f[j][k]) printf("f[%d][%d][%d] = %lld\n", i, j, k, f[j][k]);
}
LL ans = 0;
for(int j = jl[n]; j <= jr[n]; j++) for(int k = kl[n]; k <= kr[n]; k++)
if(!j && !k) (ans += f[j][k] * 3) %= MOD;
else (ans += f[j][k] * 6) %= MOD;
printf("%lld\n", ans);
}
return 0;
} /*
1
9 3
2 3 2
1 9 2
2 4 2
1
9 2
2 3 2
1 9 2
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7144kb
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: 3ms
memory: 7172kb
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: 3ms
memory: 7200kb
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: 68ms
memory: 22872kb
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: 73ms
memory: 22980kb
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: 135ms
memory: 62536kb
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: 145ms
memory: 62844kb
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: -100
Memory Limit Exceeded
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