QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402855 | #1286. Ternary String Counting | Eray | WA | 3ms | 7212kb | C++14 | 2.6kb | 2024-05-01 16:43:08 | 2024-05-01 16:43:09 |
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 = 1; 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();
}
// 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
5 2
1 3 3
4 5 1
*/
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 7212kb
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: -100
Wrong Answer
time: 3ms
memory: 7148kb
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 1146 0 0 972 2925 9 6579 927 0 0 0 0 0 0 0 0 6 0 3 0 0 0 96 0 6 0 3 0 0 0 9 0 189 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 24 0 0 0 0 0 0 0 0 0 0 0 1992 0 0 450 0 162 1842 0 0 0 0 0 54 0 27 0 0 0 0 1302 0 1899 324 0 0 42 42 0 0 60 6 63 0 0 0 0 0 0 0 0 243 8...
result:
wrong answer 9th words differ - expected: '768', found: '1146'