#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
const int mod = 1000000007;
ll n,s,e;
ll dp[N][N];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
/*freopen("kangaroo.in","r",stdin);
freopen("kangaroo.out","w",stdout);*/
cin >> n >> s >> e;
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
for(ll j = 1; j <= i; j++){
if(i == s){
/// create a new component at the beginning or just put it at the beginning
dp[i][j] += dp[i-1][j-1]+dp[i-1][j];
dp[i][j] %= mod;
continue;
}
if(i == e){
/// create a new component at the end or just put it at the end
dp[i][j] += dp[i-1][j-1]+dp[i-1][j];
dp[i][j] %= mod;
continue;
}
/// create a new component
dp[i][j] += (dp[i-1][j-1]*(j-(i > s)-(i > e)))%mod;
dp[i][j] %= mod;
/// we can't put new elements at the ends or the beginnings of existing components
/// merge two components - always valid
dp[i][j] += (dp[i-1][j+1]*j)%mod;
dp[i][j] %= mod;
}
}
cout << dp[n][1] << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Correct |
0 ms |
324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Correct |
0 ms |
324 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
452 KB |
Output is correct |
5 |
Correct |
1 ms |
452 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
452 KB |
Output is correct |
8 |
Correct |
1 ms |
452 KB |
Output is correct |
9 |
Correct |
0 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
448 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Correct |
0 ms |
324 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
452 KB |
Output is correct |
5 |
Correct |
1 ms |
452 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
452 KB |
Output is correct |
8 |
Correct |
1 ms |
452 KB |
Output is correct |
9 |
Correct |
0 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
448 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
1200 KB |
Output is correct |
14 |
Correct |
1 ms |
1228 KB |
Output is correct |
15 |
Correct |
1 ms |
1228 KB |
Output is correct |
16 |
Correct |
1 ms |
1228 KB |
Output is correct |
17 |
Correct |
1 ms |
1228 KB |
Output is correct |
18 |
Correct |
1 ms |
1100 KB |
Output is correct |
19 |
Correct |
1 ms |
1228 KB |
Output is correct |
20 |
Correct |
2 ms |
1216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Correct |
0 ms |
324 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
452 KB |
Output is correct |
5 |
Correct |
1 ms |
452 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
452 KB |
Output is correct |
8 |
Correct |
1 ms |
452 KB |
Output is correct |
9 |
Correct |
0 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
448 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
1200 KB |
Output is correct |
14 |
Correct |
1 ms |
1228 KB |
Output is correct |
15 |
Correct |
1 ms |
1228 KB |
Output is correct |
16 |
Correct |
1 ms |
1228 KB |
Output is correct |
17 |
Correct |
1 ms |
1228 KB |
Output is correct |
18 |
Correct |
1 ms |
1100 KB |
Output is correct |
19 |
Correct |
1 ms |
1228 KB |
Output is correct |
20 |
Correct |
2 ms |
1216 KB |
Output is correct |
21 |
Correct |
5 ms |
4556 KB |
Output is correct |
22 |
Correct |
5 ms |
4928 KB |
Output is correct |
23 |
Correct |
6 ms |
5500 KB |
Output is correct |
24 |
Correct |
34 ms |
22944 KB |
Output is correct |
25 |
Correct |
27 ms |
22888 KB |
Output is correct |
26 |
Correct |
26 ms |
22980 KB |
Output is correct |
27 |
Correct |
25 ms |
22840 KB |
Output is correct |
28 |
Correct |
16 ms |
15036 KB |
Output is correct |