#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;
#define llong long long
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rand(chrono::system_clock::now().time_since_epoch().count()); // or mt19937_64
#define rem ((llong)1e9+7)
#define UP 1
#define DOWN 0
namespace solution_51_points {
// the solution is similar to the official solution, but I don't swap cs and cf.
// I check them by hand and decrease cf if necessary.
const int maxn = 222;
llong dp[maxn][maxn][maxn][2]; // dp[n][cs][cf][dir]
// n - the number of cells in the garden.
// cs - the starting cell
// cf - the final cell
// dir - the current direction to move (UP or DOWN)
llong pref_sum[maxn][maxn][maxn][2];
// pref_sum[n][cs][cf][dir] = dp[n][1][cf][dir] + dp[n][2][cf][dir] + ... + dp[n][cs][cf][dir]
// in other words: pref_sum[n][cs][cf][dir] = sum of dp[n][1..cs][cf][dir]
// these 2 functions lazily calculate pref_sum and dp respectively.
llong cal_pref_sum(int, int, int, bool);
llong cal(int, int, int, bool);
llong cal_pref_sum(int n, int cs, int cf, bool dir) {
if (cs == 0) return 0;
llong& ans = pref_sum[n][cs][cf][dir];
if (ans == -1) ans = cal_pref_sum(n, cs - 1, cf, dir) + cal(n, cs, cf, dir);
return ans %= rem;
}
llong cal(int n, int cs, int cf, bool dir) {
llong& ans = dp[n][cs][cf][dir];
if (ans != -1) return ans;
if (cf == cs) return 0;
if (n == 2) return ((dir == DOWN and cs > cf) or (dir == UP and cs < cf));
int range_begin, range_end;
if (dir == DOWN) {
range_begin = 1;
range_end = cs - 1;
} else {
range_begin = cs;
range_end = n - 1;
}
int nxt_cf = cf - (cf > cs);
ans = cal_pref_sum(n - 1, range_end, nxt_cf, !dir);
ans += rem - cal_pref_sum(n - 1, range_begin - 1, nxt_cf, !dir);
ans %= rem;
// clog << n << ' ' << cs << ' ' << cf << ' ' << dir << ' ' << ans << endl;
return ans;
}
llong solve(int n, int cs, int cf) {
memset(dp, -1, sizeof(dp));
memset(pref_sum, -1, sizeof pref_sum);
return (cal(n, cf, cs, UP) + cal(n, cf, cs, DOWN)) % rem;
}
};
namespace solution_100_points {
const int maxn = 2020;
llong dp[maxn][maxn];
llong solve(int n, int cs, int cf) {
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
rep1(i, n) {
if (i == cs or i == cf) {
rep1(f, i) {
(dp[i][f] += dp[i - 1][f] + dp[i - 1][f - 1]) %= rem;
}
} else {
int unfilled_endpoints = int(i < cs) + int(i < cf);
rep1(f, i) {
(dp[i][f] += dp[i - 1][f - 1] * (f == 1 ? 1 : f - 1 + unfilled_endpoints)) %= rem;
(dp[i][f] += dp[i - 1][f + 1] * f) %= rem;
(dp[i][f] += dp[i - 1][f] * (2 * f + unfilled_endpoints - 2)) %= rem;
}
}
}
return dp[n][1];
}
};
int main(void) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// using namespace solution_51_points;
using namespace solution_100_points;
int n, cs, cf;
cin >> n >> cs >> cf;
cout << solve(n, cs, cf);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
32248 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
32248 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
32248 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
32248 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
32248 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
32248 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
32248 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
32248 KB |
Output isn't correct |
