ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#204047 | #317. count | tkswls | 100 | 141ms | 32656kb | C++11 | 2.6kb | 2024-04-06 10:04:52 | 2024-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'