#include <bits/stdc++.h>
#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
using namespace std;
typedef long long LL;
const int N = 2e3 + 10;
const int BASE = 1e9 + 7;
int n, s, t;
int dp[N][N][2][2];
void Update(int &a, int b) {
a += b; if (a >= BASE) a -= BASE;
}
LL P2(LL n) {
return n * (n - 1) % BASE;
}
int Compute(int i, int j, int L, int R) {
if (j < 0) return 0;
if (i == n) return (j == 0) ? 1 : 0;
int &ans = dp[i][j][L][R];
if (ans != -1) return ans;
ans = 0;
if (i == s) {
Update(ans, Compute(i + 1, j, 1, R));
Update(ans, (LL)j * Compute(i + 1, j - 1, 1, R) % BASE);
} else if (i == t) {
Update(ans, Compute(i + 1, j, L, 1));
Update(ans, (LL)j * Compute(i + 1, j - 1, L, 1) % BASE);
} else {
Update(ans, Compute(i + 1, j + 1, L, R));
if (L == 1) Update(ans, (LL)j * Compute(i + 1, j - 1, L, R) % BASE);
if (R == 1) Update(ans, (LL)j * Compute(i + 1, j - 1, L, R) % BASE);
Update(ans, P2(j) * Compute(i + 1, j - 1, L, R) % BASE);
}
return ans;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // LOCAL
scanf("%d%d%d", &n, &s, &t);
memset(dp, -1, sizeof dp);
printf("%d", Compute(1, 0, 0, 0));
return 0;
}
Compilation message
kangaroo.cpp: In function 'int main()':
kangaroo.cpp:54:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &s, &t);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
65140 KB |
Output is correct |
2 |
Correct |
9 ms |
65140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
65140 KB |
Output is correct |
2 |
Correct |
9 ms |
65140 KB |
Output is correct |
3 |
Correct |
3 ms |
65140 KB |
Output is correct |
4 |
Correct |
6 ms |
65140 KB |
Output is correct |
5 |
Correct |
3 ms |
65140 KB |
Output is correct |
6 |
Correct |
6 ms |
65140 KB |
Output is correct |
7 |
Correct |
0 ms |
65140 KB |
Output is correct |
8 |
Correct |
6 ms |
65140 KB |
Output is correct |
9 |
Correct |
13 ms |
65140 KB |
Output is correct |
10 |
Correct |
3 ms |
65140 KB |
Output is correct |
11 |
Correct |
9 ms |
65140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
65140 KB |
Output is correct |
2 |
Correct |
9 ms |
65140 KB |
Output is correct |
3 |
Correct |
3 ms |
65140 KB |
Output is correct |
4 |
Correct |
6 ms |
65140 KB |
Output is correct |
5 |
Correct |
3 ms |
65140 KB |
Output is correct |
6 |
Correct |
6 ms |
65140 KB |
Output is correct |
7 |
Correct |
0 ms |
65140 KB |
Output is correct |
8 |
Correct |
6 ms |
65140 KB |
Output is correct |
9 |
Correct |
13 ms |
65140 KB |
Output is correct |
10 |
Correct |
3 ms |
65140 KB |
Output is correct |
11 |
Correct |
9 ms |
65140 KB |
Output is correct |
12 |
Correct |
6 ms |
65140 KB |
Output is correct |
13 |
Correct |
9 ms |
65140 KB |
Output is correct |
14 |
Correct |
0 ms |
65140 KB |
Output is correct |
15 |
Correct |
9 ms |
65140 KB |
Output is correct |
16 |
Correct |
0 ms |
65140 KB |
Output is correct |
17 |
Correct |
6 ms |
65140 KB |
Output is correct |
18 |
Correct |
3 ms |
65140 KB |
Output is correct |
19 |
Correct |
9 ms |
65140 KB |
Output is correct |
20 |
Correct |
9 ms |
65140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
65140 KB |
Output is correct |
2 |
Correct |
9 ms |
65140 KB |
Output is correct |
3 |
Correct |
3 ms |
65140 KB |
Output is correct |
4 |
Correct |
6 ms |
65140 KB |
Output is correct |
5 |
Correct |
3 ms |
65140 KB |
Output is correct |
6 |
Correct |
6 ms |
65140 KB |
Output is correct |
7 |
Correct |
0 ms |
65140 KB |
Output is correct |
8 |
Correct |
6 ms |
65140 KB |
Output is correct |
9 |
Correct |
13 ms |
65140 KB |
Output is correct |
10 |
Correct |
3 ms |
65140 KB |
Output is correct |
11 |
Correct |
9 ms |
65140 KB |
Output is correct |
12 |
Correct |
6 ms |
65140 KB |
Output is correct |
13 |
Correct |
9 ms |
65140 KB |
Output is correct |
14 |
Correct |
0 ms |
65140 KB |
Output is correct |
15 |
Correct |
9 ms |
65140 KB |
Output is correct |
16 |
Correct |
0 ms |
65140 KB |
Output is correct |
17 |
Correct |
6 ms |
65140 KB |
Output is correct |
18 |
Correct |
3 ms |
65140 KB |
Output is correct |
19 |
Correct |
9 ms |
65140 KB |
Output is correct |
20 |
Correct |
9 ms |
65140 KB |
Output is correct |
21 |
Correct |
13 ms |
65140 KB |
Output is correct |
22 |
Correct |
19 ms |
65140 KB |
Output is correct |
23 |
Correct |
16 ms |
65140 KB |
Output is correct |
24 |
Correct |
116 ms |
65200 KB |
Output is correct |
25 |
Correct |
136 ms |
65204 KB |
Output is correct |
26 |
Correct |
126 ms |
65200 KB |
Output is correct |
27 |
Correct |
126 ms |
65196 KB |
Output is correct |
28 |
Correct |
66 ms |
65152 KB |
Output is correct |