#include <bits/stdc++.h>
using namespace std;
#define cerr cout
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const int inf = 1e9 + 7;
string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
int dp[2][51][51];
int cdp[2][51][51];
int f(int, int, int, int);
int g(int t, int n, int l, int r) {
if (l <= 0) return 0;
int &ans = cdp[t][n][l];
if (~ans) return ans;
ans = f(t, n, l, r) + g(t, n, l-1, r);
if (ans >= inf) ans -= inf;
return ans;
}
int f(int t, int n, int l, int r) {
if (l > r) l=n-l+1,r=n-r+1, t^=1;
if (l == r) return 0;
if (n == 2) return t == 1;
int &ans = dp[t][n][l];
if (~ans) return ans;
ans = 0;
if (t == 0) {
ans = g(1, n-1, l-1, r-1);
// FOR (i, 1, l - 1) {
// ans += f(1, n-1, i, r-1);
// if (ans >= inf) ans -= inf;
// }
} else {
ans = g(0, n-1, n-1, r-1) - g(0, n-1, l-1, r-1);
if (ans < 0) ans += inf;
// FOR (i, l+1, n) {
// ans += f(0, n-1, i-1, r-1);
// if (ans >= inf) ans -= inf;
// }
}
return ans;
}
int F(int n, int l, int r) {
return (f(0,n,l,r) + f(1,n,l,r))%inf;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
memset(dp, -1, sizeof dp);
memset(cdp, -1, sizeof cdp);
int n, l, r; cin >> n >> l >> r;
cout << F(n,l,r) << "\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
