제출 #105363

#제출 시각아이디문제언어결과실행 시간메모리
105363the_art_of_war캥거루 (CEOI16_kangaroo)C++14
100 / 100
147 ms64764 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int inf_int = 1e9 + 100; const ll inf_ll = 1e15; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef long double dbl; #define pb push_back const double pi = 3.1415926535898; #define dout if(debug) cout #define fi first #define se second #define sp setprecision #define sz(a) (int(a.size())) #define all(a) a.begin(),a.end() bool debug = 0; const int MAXN = 1e5 + 100; const int LOG = 20; const int mod = 1e9 + 7; const int MX = 1e6 + 100; typedef long long li; const li MOD = 1000000000949747713ll; int N, S, E; ll dp[2010][1020][2][2]; ll get(int i, int comp, int le, int ri) { if (comp < 0) return 0; if (2 * comp + 1 > N) return 0; if (dp[i][comp][le][ri] != -1) return dp[i][comp][le][ri]; ll &res = dp[i][comp][le][ri]; res = 0; if (i == N - 1) { if (comp == 0) { res = 1; //check } return res; } if (i == S) { //just res += get(i + 1, comp, 1, ri); //conn res += get(i + 1, comp - 1, 1, ri) * comp; } else if (i == E) { res += get(i + 1, comp, le, 1); res += get(i + 1, comp - 1, le, 1) * comp; } else { //just create res += get(i + 1, comp + 1, le, ri); //connect res += get(i + 1, comp - 1, le, ri) * (1ll * comp * (comp - 1)) % mod; if (le > 0) { //connect res += get(i + 1, comp - 1, le, ri) * comp; } if (ri > 0) { //connect res += get(i + 1, comp - 1, le, ri) * comp; } } res%=mod; return res; } void solve() { memset(dp,-1,sizeof dp); cin >> N >> S >> E; S--; E--; cout << get(0,0,0,0)<<"\n"; } signed main() { #ifdef zxc debug = 1; freopen("../input.txt", "r", stdin); #else #endif //zxc ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.setf(ios::fixed); cout.precision(20); int t = 1; while (t--) solve(); dout << (1.0 * clock() / CLOCKS_PER_SEC) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...