#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint MOD = 1e9 + 7;
int N, S, T;
lint memo[2005][2005][2][2];
lint dp(int n, int comp, int lend, int rend) {
if (comp < 0) {
return 0;
}
if (n == N - 1) {
return comp == 0 ? 1 : 0; // use last piece to merge S and T component
}
lint &res = memo[n][comp][lend][rend];
if (res != -1) {
return res;
}
res = 0;
if (n == S) {
res += dp(n + 1, comp, 1, rend); // make new component
res += dp(n + 1, comp - 1, 1, rend) * comp; // connect a component to left end
} else if (n == T) {
res += dp(n + 1, comp, lend, 1); // make new component
res += dp(n + 1, comp - 1, lend, 1) * comp; // connect a component to right end
} else {
res += dp(n + 1, comp + 1, lend, rend); // add a new component
res += dp(n + 1, comp - 1, lend, rend) * comp * (comp - 1); // merge two components
res += dp(n + 1, comp - 1, lend, rend) * comp * lend; // connect component to left end
res += dp(n + 1, comp - 1, lend, rend) * comp * rend; // connect component to right end
}
res %= MOD;
return res;
}
int main() {
memset(memo, -1, sizeof(memo));
cin >> N >> S >> T;
S--, T--;
cout << dp(0, 0, 0, 0) << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
107 ms |
126352 KB |
Output is correct |
2 |
Correct |
115 ms |
126156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
107 ms |
126352 KB |
Output is correct |
2 |
Correct |
115 ms |
126156 KB |
Output is correct |
3 |
Correct |
118 ms |
126272 KB |
Output is correct |
4 |
Correct |
106 ms |
126176 KB |
Output is correct |
5 |
Correct |
106 ms |
126200 KB |
Output is correct |
6 |
Correct |
106 ms |
126136 KB |
Output is correct |
7 |
Correct |
107 ms |
126172 KB |
Output is correct |
8 |
Correct |
106 ms |
126120 KB |
Output is correct |
9 |
Correct |
106 ms |
126120 KB |
Output is correct |
10 |
Correct |
108 ms |
126132 KB |
Output is correct |
11 |
Correct |
106 ms |
126200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
107 ms |
126352 KB |
Output is correct |
2 |
Correct |
115 ms |
126156 KB |
Output is correct |
3 |
Correct |
118 ms |
126272 KB |
Output is correct |
4 |
Correct |
106 ms |
126176 KB |
Output is correct |
5 |
Correct |
106 ms |
126200 KB |
Output is correct |
6 |
Correct |
106 ms |
126136 KB |
Output is correct |
7 |
Correct |
107 ms |
126172 KB |
Output is correct |
8 |
Correct |
106 ms |
126120 KB |
Output is correct |
9 |
Correct |
106 ms |
126120 KB |
Output is correct |
10 |
Correct |
108 ms |
126132 KB |
Output is correct |
11 |
Correct |
106 ms |
126200 KB |
Output is correct |
12 |
Correct |
107 ms |
126200 KB |
Output is correct |
13 |
Correct |
111 ms |
126200 KB |
Output is correct |
14 |
Correct |
106 ms |
126284 KB |
Output is correct |
15 |
Correct |
107 ms |
126224 KB |
Output is correct |
16 |
Correct |
102 ms |
126200 KB |
Output is correct |
17 |
Correct |
107 ms |
126232 KB |
Output is correct |
18 |
Correct |
107 ms |
126184 KB |
Output is correct |
19 |
Correct |
108 ms |
126200 KB |
Output is correct |
20 |
Correct |
107 ms |
126148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
107 ms |
126352 KB |
Output is correct |
2 |
Correct |
115 ms |
126156 KB |
Output is correct |
3 |
Correct |
118 ms |
126272 KB |
Output is correct |
4 |
Correct |
106 ms |
126176 KB |
Output is correct |
5 |
Correct |
106 ms |
126200 KB |
Output is correct |
6 |
Correct |
106 ms |
126136 KB |
Output is correct |
7 |
Correct |
107 ms |
126172 KB |
Output is correct |
8 |
Correct |
106 ms |
126120 KB |
Output is correct |
9 |
Correct |
106 ms |
126120 KB |
Output is correct |
10 |
Correct |
108 ms |
126132 KB |
Output is correct |
11 |
Correct |
106 ms |
126200 KB |
Output is correct |
12 |
Correct |
107 ms |
126200 KB |
Output is correct |
13 |
Correct |
111 ms |
126200 KB |
Output is correct |
14 |
Correct |
106 ms |
126284 KB |
Output is correct |
15 |
Correct |
107 ms |
126224 KB |
Output is correct |
16 |
Correct |
102 ms |
126200 KB |
Output is correct |
17 |
Correct |
107 ms |
126232 KB |
Output is correct |
18 |
Correct |
107 ms |
126184 KB |
Output is correct |
19 |
Correct |
108 ms |
126200 KB |
Output is correct |
20 |
Correct |
107 ms |
126148 KB |
Output is correct |
21 |
Correct |
115 ms |
126276 KB |
Output is correct |
22 |
Correct |
142 ms |
126200 KB |
Output is correct |
23 |
Correct |
119 ms |
126212 KB |
Output is correct |
24 |
Correct |
219 ms |
126328 KB |
Output is correct |
25 |
Correct |
213 ms |
126428 KB |
Output is correct |
26 |
Correct |
218 ms |
126352 KB |
Output is correct |
27 |
Correct |
232 ms |
126368 KB |
Output is correct |
28 |
Correct |
172 ms |
126360 KB |
Output is correct |