#include <bits/stdc++.h>
using namespace std;
const long long MOD = (1e9)+7;
inline void add(int& a, int b) { a = (a + b) % MOD; }
inline int mul(int a, int b) { return 1ll * a * b % MOD; }
int n, s, e, dp[2001][2001];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> s >> e;
dp[0][0] = 1;
for(int i = 0; i < n; i++) for(int j = 0; j <= i; j++) {
if(i+1 == n) {
add(dp[i+1][j], dp[i][j]);
continue;
}
if(i+1 == s || i+1 == e) { // automatically decrease j by 1, since s, e not counted
add(dp[i+1][j], dp[i][j]); // new cc
if(j) add(dp[i+1][j-1], mul(dp[i][j], j)); // append to start/end of some cc
} else {
add(dp[i+1][j+1], dp[i][j]); // new cc
if(j >= 2) add(dp[i+1][j-1], mul(dp[i][j], j*(j-1))); // join two non-empty cc
if(i+1 > s && j) add(dp[i+1][j-1], mul(dp[i][j], j)); // append to start's cc
if(i+1 > e && j) add(dp[i+1][j-1], mul(dp[i][j], j)); // append to end's cc
}
}
cout << dp[n][0];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
17820 KB |
Output is correct |
2 |
Correct |
0 ms |
17820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
17820 KB |
Output is correct |
2 |
Correct |
0 ms |
17820 KB |
Output is correct |
3 |
Correct |
0 ms |
17820 KB |
Output is correct |
4 |
Correct |
0 ms |
17820 KB |
Output is correct |
5 |
Correct |
0 ms |
17820 KB |
Output is correct |
6 |
Correct |
0 ms |
17820 KB |
Output is correct |
7 |
Correct |
0 ms |
17820 KB |
Output is correct |
8 |
Correct |
0 ms |
17820 KB |
Output is correct |
9 |
Correct |
0 ms |
17820 KB |
Output is correct |
10 |
Correct |
0 ms |
17820 KB |
Output is correct |
11 |
Correct |
0 ms |
17820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
17820 KB |
Output is correct |
2 |
Correct |
0 ms |
17820 KB |
Output is correct |
3 |
Correct |
0 ms |
17820 KB |
Output is correct |
4 |
Correct |
0 ms |
17820 KB |
Output is correct |
5 |
Correct |
0 ms |
17820 KB |
Output is correct |
6 |
Correct |
0 ms |
17820 KB |
Output is correct |
7 |
Correct |
0 ms |
17820 KB |
Output is correct |
8 |
Correct |
0 ms |
17820 KB |
Output is correct |
9 |
Correct |
0 ms |
17820 KB |
Output is correct |
10 |
Correct |
0 ms |
17820 KB |
Output is correct |
11 |
Correct |
0 ms |
17820 KB |
Output is correct |
12 |
Correct |
0 ms |
17820 KB |
Output is correct |
13 |
Correct |
0 ms |
17820 KB |
Output is correct |
14 |
Correct |
0 ms |
17820 KB |
Output is correct |
15 |
Correct |
0 ms |
17820 KB |
Output is correct |
16 |
Correct |
0 ms |
17820 KB |
Output is correct |
17 |
Correct |
0 ms |
17820 KB |
Output is correct |
18 |
Correct |
0 ms |
17820 KB |
Output is correct |
19 |
Correct |
0 ms |
17820 KB |
Output is correct |
20 |
Correct |
0 ms |
17820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
17820 KB |
Output is correct |
2 |
Correct |
0 ms |
17820 KB |
Output is correct |
3 |
Correct |
0 ms |
17820 KB |
Output is correct |
4 |
Correct |
0 ms |
17820 KB |
Output is correct |
5 |
Correct |
0 ms |
17820 KB |
Output is correct |
6 |
Correct |
0 ms |
17820 KB |
Output is correct |
7 |
Correct |
0 ms |
17820 KB |
Output is correct |
8 |
Correct |
0 ms |
17820 KB |
Output is correct |
9 |
Correct |
0 ms |
17820 KB |
Output is correct |
10 |
Correct |
0 ms |
17820 KB |
Output is correct |
11 |
Correct |
0 ms |
17820 KB |
Output is correct |
12 |
Correct |
0 ms |
17820 KB |
Output is correct |
13 |
Correct |
0 ms |
17820 KB |
Output is correct |
14 |
Correct |
0 ms |
17820 KB |
Output is correct |
15 |
Correct |
0 ms |
17820 KB |
Output is correct |
16 |
Correct |
0 ms |
17820 KB |
Output is correct |
17 |
Correct |
0 ms |
17820 KB |
Output is correct |
18 |
Correct |
0 ms |
17820 KB |
Output is correct |
19 |
Correct |
0 ms |
17820 KB |
Output is correct |
20 |
Correct |
0 ms |
17820 KB |
Output is correct |
21 |
Correct |
0 ms |
17820 KB |
Output is correct |
22 |
Correct |
3 ms |
17820 KB |
Output is correct |
23 |
Correct |
3 ms |
17820 KB |
Output is correct |
24 |
Correct |
29 ms |
17820 KB |
Output is correct |
25 |
Correct |
33 ms |
17820 KB |
Output is correct |
26 |
Correct |
33 ms |
17820 KB |
Output is correct |
27 |
Correct |
39 ms |
17820 KB |
Output is correct |
28 |
Correct |
16 ms |
17820 KB |
Output is correct |