#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
//be careful about edges being bound already
if (cur == cs) {
//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+1);
}
res %= mod;
return dp[cur][groups] = res;
}
else if (cur == cf) {
//do the same thing as with cs
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)
res += mult(numopen, go(cur+1, groups+1));
res %= mod;
//option 2 : bind me to one guy
int numbind = 2 * numopen;
numbind -= 2 - numedge; //if there is no edge then that open spot does not get another
if (groups >= 1) res += mult(numbind, go(cur+1, groups));
res %= mod;
//option 3 : bind 2 groups together
numbind = numopen;
numbind -= 2 - numedge;
if (groups >= 2) res += mult(numbind, go(cur+1, groups-1));
res %= mod;
return dp[cur][groups] = res;
}
}
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 |
Incorrect |
14 ms |
16368 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
16120 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
16368 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
16120 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
16368 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
16120 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
16368 KB |
Output isn't correct |
