UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#204047#317. counttkswls100141ms32656kbC++112.6kb2024-04-06 10:04:522024-04-06 12:11:19

answer

#include<bits/stdc++.h>
#define int long long
#pragma GCC optimize(2)
using namespace std;
int n, x, y, f[2005][2005], ans;
const int mod = 1000000007, inv2 = 500000004;
inline int calc(int p, int q) {
	if (p <= q) return 0;
	static int cnt;
	cnt = 0;
	cnt = (p - q) * (p - q - 1)  % mod;
	cnt += q * (p - q) % mod;
	cnt %= mod;
	return cnt;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> x >> y;
	memset(f, 0, sizeof(f));
	if (n & 1) {
		f[0][0] = 1;
		for (int i = 1; i < n; i++) {
			if (i == x || i == y) {
				for (int j = 1; j <= i; j++) {
					f[i][j] = f[i - 1][j - 1];
				}
			} else {
				int op = (i > x) + (i > y);
				for (int j = 1; j <= i; j++) {
					f[i][j] = (f[i - 1][j - 1] + f[i - 1][j + 1] * calc(j + 1, op) % mod) % mod;
				}
			}
		}
		if (y == n) {
			ans = f[n - 1][1];
		} else if (x != n) {
			ans = f[n - 1][2];
		}
		memset(f, 0, sizeof(f));
		f[n + 1][0] = 1;
		for (int i = n; i > 1; i--) {
			if (i == x || i == y) {
				for (int j = 1; j <= (n - i + 1); j++) {
					f[i][j] = f[i + 1][j - 1];
				}
			} else {
				int op = (i < x) + (i < y);
				for (int j = 1; j <= (n - i + 1); j++) {
					f[i][j] = (f[i + 1][j - 1] + f[i + 1][j + 1] * calc(j + 1, op) % mod) % mod;
				}
			}
		}
		if (y == 1) {
			ans += f[2][1];
		} else if (x != 1) {
			ans += f[2][2];
		}
		cout << ans % mod;
	} else {
		f[0][0] = 1;
		for (int i = 1; i < n; i++) {
			if (i == x) {
				for (int j = 1; j <= i; j++) {
					f[i][j] = f[i - 1][j - 1];
				}
			} else if (i == y) {
				int op = (i > x);
				for (int j = 1; j <= i; j++) {
					f[i][j] = f[i - 1][j] * (j - op) % mod;
				}
			} else {
				int op = (i > x) + (i > y);
				for (int j = 1; j <= i; j++) {
					f[i][j] = (f[i - 1][j - 1] + f[i - 1][j + 1] * calc(j + 1, op) % mod) % mod;
				}
			}
		}
		if (y == n) {
			ans = f[n - 1][1];
		} else if (x != n) {
			ans = f[n - 1][2];
		}
		memset(f, 0, sizeof(f));
		f[n + 1][0] = 1;
		for (int i = n; i > 1; i--) {
			if (i == x ) {
				for (int j = 1; j <= (n - i + 1); j++) {
					f[i][j] = f[i + 1][j - 1];
				}
			} else if (i == y) {
				int op = (i < x);
				for (int j = 1; j <= (n - i + 1); j++) {
					f[i][j] = f[i + 1][j] * (j - op) % mod;
				}
			} else {
				int op = (i < x) + (i < y);
				for (int j = 1; j <= (n - i + 1); j++) {
					f[i][j] = (f[i + 1][j - 1] + f[i + 1][j + 1] * calc(j + 1, op) % mod) % mod;
				}
			}
		}
		if (y == 1) {
			ans += f[2][1];
		} else if (x != 1) {
			ans += f[2][2];
		}
		cout << ans % mod;
	}
}
//好多特判,纯纯狗屎

//5 3 1

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 7ms
memory: 32656kb

input:

14 14 3

output:

2652244

result:

ok single line: '2652244'

Test #2:

score: 0
Accepted
time: 8ms
memory: 32652kb

input:

15 8 9

output:

22368256

result:

ok single line: '22368256'

Subtask #2:

score: 40
Accepted

Test #3:

score: 40
Accepted
time: 4ms
memory: 32652kb

input:

123 12 23

output:

717729765

result:

ok single line: '717729765'

Test #4:

score: 0
Accepted
time: 12ms
memory: 32652kb

input:

200 1 200

output:

374145341

result:

ok single line: '374145341'

Test #5:

score: 0
Accepted
time: 7ms
memory: 32652kb

input:

199 23 1

output:

793642422

result:

ok single line: '793642422'

Subtask #3:

score: 40
Accepted

Test #6:

score: 40
Accepted
time: 44ms
memory: 32656kb

input:

2000 666 1333

output:

993781645

result:

ok single line: '993781645'

Test #7:

score: 0
Accepted
time: 16ms
memory: 32656kb

input:

800 1 800

output:

169429350

result:

ok single line: '169429350'

Test #8:

score: 0
Accepted
time: 43ms
memory: 32652kb

input:

1991 198 677

output:

155058730

result:

ok single line: '155058730'