#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define ll long long
#define maxn 2010
int dp[maxn][maxn];
int N;
int cs, cf;
int mult(ll a, ll b) {
return (a*b)%mod;
}
int go(int cur, int groups) {
if (cur == N+1) {
if (groups == 1) return 1;
return 0; //must have 1 group or else we are bad
}
if (groups < 0) return 0;
if (dp[cur][groups] != -1) {
return dp[cur][groups]; //already processed this value
}
//handle cs and cf separately (i think they might be equivalent though)
//be careful about edges being bound already
if (cur == cs || cur == cf) {
//bind me to my correct side (whatever it is)
int res = 0;
//option 1 : add me loosely to my edge
res += go(cur+1, groups+1);
res %= mod;
//option 2 : bind me to the guy when you add me on the edge
if (groups > 0) {
res += go(cur+1, groups);
}
res %= mod;
return dp[cur][groups] = res;
}
else {
int numedge = 0; //how many edges there are
if (cur > cs) numedge++;
if (cur > cf) numedge++;
int numopen = groups+1;
numopen -= numedge; //one less group here
int res = 0;
//option 1 : add me loosely (do it in any open spot, will be surrounded by 2 greater than it)
res += mult(numopen, go(cur+1, groups+1));
res %= mod;
//option 2 : bind 2 groups together (will be surrounded by 2 less than it)
int numbind = numopen;
numbind -= 2 - numedge;
if (groups >= 2) res += mult(numbind, go(cur+1, groups-1));
res %= mod;
return dp[cur][groups] = res;
} //note that binding to just one group is illegal
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> cs >> cf;
for (int i = 0; i < maxn; i++) {
fill(dp[i], dp[i]+maxn, -1);
}
int ans = go(1, 0);
cout << ans << endl;
cin >> ans;
}
//given N, cs and cf
// 1 <= cs <= N
// calculate number of ways to go cs to cf if you alternate between left and right
// 2 <= N <= 2000
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
16120 KB |
Output is correct |
2 |
Correct |
14 ms |
16120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
16120 KB |
Output is correct |
2 |
Correct |
14 ms |
16120 KB |
Output is correct |
3 |
Correct |
18 ms |
16284 KB |
Output is correct |
4 |
Correct |
17 ms |
16396 KB |
Output is correct |
5 |
Correct |
15 ms |
16396 KB |
Output is correct |
6 |
Correct |
14 ms |
16396 KB |
Output is correct |
7 |
Correct |
15 ms |
16396 KB |
Output is correct |
8 |
Correct |
15 ms |
16396 KB |
Output is correct |
9 |
Correct |
16 ms |
16396 KB |
Output is correct |
10 |
Correct |
15 ms |
16396 KB |
Output is correct |
11 |
Correct |
14 ms |
16396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
16120 KB |
Output is correct |
2 |
Correct |
14 ms |
16120 KB |
Output is correct |
3 |
Correct |
18 ms |
16284 KB |
Output is correct |
4 |
Correct |
17 ms |
16396 KB |
Output is correct |
5 |
Correct |
15 ms |
16396 KB |
Output is correct |
6 |
Correct |
14 ms |
16396 KB |
Output is correct |
7 |
Correct |
15 ms |
16396 KB |
Output is correct |
8 |
Correct |
15 ms |
16396 KB |
Output is correct |
9 |
Correct |
16 ms |
16396 KB |
Output is correct |
10 |
Correct |
15 ms |
16396 KB |
Output is correct |
11 |
Correct |
14 ms |
16396 KB |
Output is correct |
12 |
Correct |
15 ms |
16396 KB |
Output is correct |
13 |
Correct |
15 ms |
16396 KB |
Output is correct |
14 |
Correct |
14 ms |
16396 KB |
Output is correct |
15 |
Correct |
16 ms |
16396 KB |
Output is correct |
16 |
Correct |
16 ms |
16516 KB |
Output is correct |
17 |
Correct |
15 ms |
16552 KB |
Output is correct |
18 |
Correct |
14 ms |
16552 KB |
Output is correct |
19 |
Correct |
15 ms |
16552 KB |
Output is correct |
20 |
Correct |
16 ms |
16656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
16120 KB |
Output is correct |
2 |
Correct |
14 ms |
16120 KB |
Output is correct |
3 |
Correct |
18 ms |
16284 KB |
Output is correct |
4 |
Correct |
17 ms |
16396 KB |
Output is correct |
5 |
Correct |
15 ms |
16396 KB |
Output is correct |
6 |
Correct |
14 ms |
16396 KB |
Output is correct |
7 |
Correct |
15 ms |
16396 KB |
Output is correct |
8 |
Correct |
15 ms |
16396 KB |
Output is correct |
9 |
Correct |
16 ms |
16396 KB |
Output is correct |
10 |
Correct |
15 ms |
16396 KB |
Output is correct |
11 |
Correct |
14 ms |
16396 KB |
Output is correct |
12 |
Correct |
15 ms |
16396 KB |
Output is correct |
13 |
Correct |
15 ms |
16396 KB |
Output is correct |
14 |
Correct |
14 ms |
16396 KB |
Output is correct |
15 |
Correct |
16 ms |
16396 KB |
Output is correct |
16 |
Correct |
16 ms |
16516 KB |
Output is correct |
17 |
Correct |
15 ms |
16552 KB |
Output is correct |
18 |
Correct |
14 ms |
16552 KB |
Output is correct |
19 |
Correct |
15 ms |
16552 KB |
Output is correct |
20 |
Correct |
16 ms |
16656 KB |
Output is correct |
21 |
Correct |
20 ms |
16660 KB |
Output is correct |
22 |
Correct |
25 ms |
16664 KB |
Output is correct |
23 |
Correct |
24 ms |
16668 KB |
Output is correct |
24 |
Correct |
92 ms |
16772 KB |
Output is correct |
25 |
Correct |
92 ms |
16772 KB |
Output is correct |
26 |
Correct |
79 ms |
16772 KB |
Output is correct |
27 |
Correct |
96 ms |
16772 KB |
Output is correct |
28 |
Correct |
53 ms |
16772 KB |
Output is correct |