QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402871#1286. Ternary String CountingErayML 145ms62844kbC++142.7kb2024-05-01 17:03:142024-05-01 17:03:14

Judging History

你现在查看的是最新测评结果

  • [2024-05-01 17:03:14]
  • 评测
  • 测评结果:ML
  • 用时:145ms
  • 内存:62844kb
  • [2024-05-01 17:03:14]
  • 提交

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

result: