QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#236311#1286. Ternary String Countingle6666WA 1ms4016kbC++143.0kb2023-11-03 20:27:342023-11-03 20:27:35

Judging History

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

  • [2023-11-03 20:27:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4016kb
  • [2023-11-03 20:27:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MOD = 1e9 + 7;
const int MAXN = 5e3 + 5;
int n, m, lj[MAXN], rj[MAXN], lk[MAXN], rk[MAXN];
struct Limit { int l, r, x; } lim[MAXN];
int nl[MAXN], nr[MAXN];
struct LL {
	ll num = 0;
	LL operator+ (LL other) { return { (num + other.num) % MOD }; }
	LL operator+ (ll k) { return { (num + k) % MOD }; }
	LL operator- (LL other) { return { (num - other.num + MOD) % MOD }; }
	void operator+= (LL other) { *this = *this + other; }
	void operator-= (LL other) { *this = *this - other; }
	LL operator= (ll k) { num = k; return *this; }
};
LL f[MAXN][MAXN], hang[MAXN], lie[MAXN];

void test() {
	for (int i = 0 ; i <= n; i++) {
		for (int j = 0; j <= n; j++) printf("%lld ", f[i][j].num);
		printf("\n");
	}
	printf("\n");
}

void del(int x, int y) {
	if (x || y) hang[x] -= f[x][y], lie[y] -= f[x][y], f[x][y] = 0;
	else if (!x && !y) f[0][0] = 0;
//	else if (!y) lie[0] -= f[x][0], f[x][0] = 0;
}

bool in(int x, int y) { return nl[x] <= y && y <= nr[x]; }

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= m; i++) scanf("%d%d%d", &lim[i].l, &lim[i].r, &lim[i].x);
		for (int i = 1; i <= n; i++) lj[i] = lk[i] = nl[i] = 0, rj[i] = rk[i] = nr[i] = n;
		for (int i = 0; i <= n; i++) {
			hang[i] = lie[i] = 0;
			for (int j = 0; j <= n; j++)
				f[i][j] = 0;
		}
		for (int i = 1; i <= m; i++) {
			auto [l, r, x] = lim[i];
			if (x == 1) rj[r] = min(rj[r], l - 1);
			else if (x == 2) lj[r] = max(lj[r], l), rk[r] = min(rk[r], l - 1);
			else lk[r] = max(lk[r], l);
		}
		bool flag = false;
		for (int i = 1; i <= n; i++)
			if (lj[i] > rj[i] || lk[i] > rk[i])
				flag = true;
		if (flag) { printf("0\n"); continue; }
//		f[0][0] = hang[0] = lie[0] = 1;
		f[0][0] = 1;
		for (int i = 2; i <= n; i++) {
			if (in(i - 1, 0)) f[i - 1][0] = lie[0] + 1, hang[i - 1] += f[i - 1][0], lie[0] += f[i - 1][0];
			for (int j = 1; j < i - 1; j++) /*if (in(i - 1, j))*/ f[i - 1][j] = hang[j] + lie[j];
			for (int j = 1; j < i - 1; j++) hang[i - 1] += f[i - 1][j], lie[j] += f[i - 1][j];
			for (int j = 0; j < lj[i]; j++)
				for ( ; nl[j] <= nr[j]; nl[j]++)
					del(j, nl[j]);
			for (int j = lj[i]; j <= rj[i]; j++) {
				for ( ; nl[j] <= nr[j] && nl[j] < lk[i]; nl[j]++)
					del(j, nl[j]);
				for ( ; nl[j] <= nr[j] && rk[i] < nr[j]; nr[j]--)
					del(j, nr[j]);
			}
			for (int j = rj[i] + 1; j <= n; j++)
				for ( ; nl[j] <= nr[j]; nl[j]++)
					del(j, nl[j]);
//			test();
		}
		ll ans = 0;
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++)
				if (i == 0 && j == 0) ans = (ans + f[i][j].num * 3) % MOD;
				else if (i == 0 || j == 0) ans = (ans + f[i][j].num * 6) % MOD;
				else ans = (ans + f[i][j].num * 6) % MOD;
		printf("%lld\n", ans);
//		for (int i = 1; i <= n; i++) {
//			printf("%d %d %d %d\n", lk[i], rk[i], lj[i], rj[i]);
//		}
	}
	return 0;
}

/*

2
5 3
1 5 3
3 4 2
1 4 3
4 3
2 4 2
1 4 1
2 3 3

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4016kb

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: 1ms
memory: 3944kb

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
3
0
46875
57
9
0
14925
3
3
2901
2925
561
24003
27255
3
0
3
3
3
0
9
0
3
3405
165
0
0
0
423
0
9
0
273
9
4089
3
3
3
195
3
3
705
2919
75
3
3
0
0
7347
0
3
3
7779
327
8751
489
9
0
3
3
3
3549
3
3
0
27
0
0
75
2109
3
3
9
31269
0
0
153
4827
3
2163
453
3
219
10899
0
0
3
0
33
165
0
111
3
3
5691
3
8745
3
11...

result:

wrong answer 3rd words differ - expected: '0', found: '3'