이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?b:gcd(b%a,a); }
#define ll /*long long*/ int
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (201)
ll mem[MAXN][MAXN][MAXN][2][2], n, cs, cf, mod=1e9+7;
ll dp(ll a, ll b, ll c, ll flag, ll lr) { // flag -> 0 means only can jump left, lr -> 0 means left of cf
if(a<0||b<0||c<0) return 0;
if(~mem[a][b][c][flag][lr]) return mem[a][b][c][flag][lr];
if(a == 0 && b == 0 && c == 0) return lr != flag;
ll x = 0;
if(lr) { // node right of cf
if(flag == 0) {
FOR(i,0,b-1) {
x += dp(a,i,c+b-i-1,1,1), x%=mod;
}
FOR(i,0,a-1) {
x += dp(i, a-i-1, b+c, 1, 0), x%=mod;
}
} else {
FOR(i,0,c-1) {
x += dp(a, b+i, c-i-1, 0, 1), x%=mod;
}
}
} else { // node left of cf
if(flag == 1) {
FOR(i,0,b-1) {
x += dp(a+i, b-i-1, c, 0, 0), x%=mod;
}
FOR(i,0,c-1) {
x += dp(a+b, i, c-i-1, 0, 1), x%=mod;
}
} else {
FOR(i,0,a-1) {
x += dp(i, a-i-1+b, c, 1, 0), x%=mod;
}
}
}
return mem[a][b][c][flag][lr]=x;
}
int main()
{
// freopen("kangaroo.in","r",stdin);
// freopen("kangaroo.out","w",stdout);
cin>>n>>cs>>cf; mmst(mem,-1);
if(cs < cf) {
cout<<(dp(cs-1, cf-cs-1, n-cf, 0, 0) + dp(cs-1, cf-cs-1, n-cf, 1, 0))%mod<<'\n';
} else {
cout<<(dp(cf-1, cs-cf-1, n-cs, 0, 1) + dp(cf-1, cs-cf-1, n-cs, 1, 1))%mod<<'\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |