Submission #900625

#TimeUsernameProblemLanguageResultExecution timeMemory
900625warner1129Kangaroo (CEOI16_kangaroo)C++17
100 / 100
33 ms488 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL template<class... T> void dbg(T... x) { char e{}; ((cerr << e << x, e = ' '), ...); } #define debug(x...) dbg(#x, '=', x, '\n') #else #define debug(...) ((void)0) #endif #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() #define ff first #define ss second using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; using i128 = __int128; using u128 = unsigned __int128; template<class T> inline constexpr T inf = numeric_limits<T>::max() / 2; constexpr int mod = 1e9 + 7, inv2 = (mod + 1) / 2; template<class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); } template<class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); } void solve() { int n, s, t; cin >> n >> s >> t; int op = s > 1; int ed = t > 1; vector dp(n + 1, array<i64, 3>{}); dp[1][0] = 1; for (int i = 2; i <= n; i++) { decltype(dp) f(n + 1, array<i64, 3>{}); for (int j = 1; j < i; j++) { if (i == s or i == t) { f[j][1] += dp[j][0]; f[j][2] += dp[j][1]; f[j + 1][0] += dp[j][0]; f[j + 1][1] += dp[j][1]; f[j + 1][2] += dp[j][2]; } else { for (int x : {0, 1, 2}) { f[j - 1][x] += dp[j][x] * (j - 1); f[j + 1][x] += dp[j][x] * (i - 1 - j + op + ed - x); } } } if (s == i) op = 0; if (t == i) ed = 0; dp.swap(f); for (auto &x : dp) for (auto &v : x) v %= mod; } cout << (dp[1][0] + dp[1][1] + dp[1][2]) % mod << '\n'; } signed main() { cin.tie(0)->sync_with_stdio(false); cin.exceptions(cin.failbit); int T = 1; // cin >> T; while (T--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...