#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n, a, b;
int add(int a, int b)
{
int x = a+b;
if(x >= mod)
x -= mod;
if(x < 0)
x += mod;
return x;
}
int main()
{
cin >> n >> a >> b;
int dp[2][n+2][n+2];
int sp[2][2][n+2][n+2];
for(int i = 1; i <= n; ++i)
if(i != a && i != b)
dp[(a < i)][i - 1 - (a < i)][b - (a < b) - (i < b)] = 1;
if(n == 2)
{
cout << 1;
return 0;
}
int ans = 0;
for(int sum = n-2; sum >= 1; --sum)
{
for(int i = 0; i <= sum; ++i)
for(int pos = 1; pos <= sum; ++pos)
{
int smaller = i;
int bigger = sum - i;
if(sum != n-2)
{
dp[0][smaller][pos] = add(sp[0][0][smaller][pos], (smaller > 0) * dp[0][smaller - 1][pos]);
dp[1][smaller][pos] = add(sp[0][1][smaller][pos], (smaller > 0) * dp[1][smaller - 1][pos]);
}
if(!dp[0][smaller][pos] && !dp[1][smaller][pos])
continue;
// cout << sum << '\n';
// cout << smaller << " " << bigger << " " << pos << '\n';
// cout << dp[0][smaller][bigger][pos] << " " << dp[1][smaller][bigger][pos] << '\n';
if(sum == 1)
{
if(smaller)
ans = add(ans, dp[1][smaller][1]);
else
ans = add(ans, dp[0][smaller][1]);
}
else
{
if(pos <= smaller)
{
sp[1][0][0][pos - 1] = add(sp[1][0][0][pos - 1], dp[1][smaller][pos]);
sp[1][0][pos - 1][pos - 1] = add(sp[1][0][pos - 1][pos - 1], -dp[1][smaller][pos]);
sp[1][0][pos][pos] = add(sp[1][0][pos][pos], dp[1][smaller][pos]);
sp[1][0][smaller][pos] = add(sp[1][0][smaller][pos], -dp[1][smaller][pos]);
sp[1][1][smaller][pos] = add(sp[1][1][smaller][pos], dp[0][smaller][pos]);
sp[1][1][sum][pos] = add(sp[1][1][sum][pos], -dp[0][smaller][pos]);
}
else
{
sp[1][0][0][pos - 1] = add(sp[1][0][0][pos - 1], dp[1][smaller][pos]);
sp[1][0][smaller][pos - 1] = add(sp[1][0][smaller][pos - 1], -dp[1][smaller][pos]);
sp[1][1][smaller][pos - 1] = add(sp[1][1][smaller][pos - 1], dp[0][smaller][pos]);
sp[1][1][pos - 1][pos - 1] = add(sp[1][1][pos - 1][pos - 1], -dp[0][smaller][pos]);
sp[1][1][pos][pos] = add(sp[1][1][pos][pos], dp[0][smaller][pos]);
sp[1][1][sum][pos] = add(sp[1][1][sum][pos], -dp[0][smaller][pos]);
}
}
}
memcpy(sp[0], sp[1], sizeof(sp[1]));
memset(sp[1], 0, sizeof(sp[1]));
/*
for(int x = 0; x <= 1; ++x)
for(int q = 0; q <= sum; ++q)
for(int p = 0; p <= sum; ++p)
sp[0][x][q][p] = sp[1][x][q][p], sp[1][x][q][p] = 0;
*/
}
cout << ans;
return 0;
}
Compilation message
kangaroo.cpp: In function 'int main()':
kangaroo.cpp:34:21: warning: unused variable 'bigger' [-Wunused-variable]
int bigger = sum - i;
^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
