QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402855#1286. Ternary String CountingErayWA 3ms7212kbC++142.6kb2024-05-01 16:43:082024-05-01 16:43:09

Judging History

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

  • [2024-05-01 16:43:09]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:7212kb
  • [2024-05-01 16:43:08]
  • 提交

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
*/

Details

Tip: Click on the bar to expand more detailed information

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'