Submission #1294276

#TimeUsernameProblemLanguageResultExecution timeMemory
1294276Zakir060Kangaroo (CEOI16_kangaroo)C++20
100 / 100
21 ms31756 KiB
#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, cs, cf; if (!(cin >> N >> cs >> cf)) return 0; if (N == 2) { cout << 1 << '\n'; return 0; } if (cs > cf) swap(cs, cf); static long long dp[2001][2001]; for (int i = 0; i <= N; ++i) for (int j = 0; j <= N; ++j) dp[i][j] = 0; dp[0][0] = 1; for (int i = 1; i < cs; ++i) { for (int c = 1; c <= i; ++c) { dp[i][c] = (dp[i][c] + dp[i-1][c-1] * 1LL * c) % MOD; } for (int c = 0; c < i; ++c) { dp[i][c] = (dp[i][c] + dp[i-1][c+1] * 1LL * c) % MOD; } } if (cs >= 1) { for (int c = 0; c <= N; ++c) { long long val = dp[cs-1][c]; if (c > 0) val = (val + dp[cs-1][c-1]) % MOD; dp[cs][c] = val; } } for (int i = cs + 1; i < cf; ++i) { for (int c = 1; c <= i; ++c) { dp[i][c] = (dp[i][c] + dp[i-1][c-1] * 1LL * (c - 1)) % MOD; } for (int c = 0; c < i; ++c) { dp[i][c] = (dp[i][c] + dp[i-1][c+1] * 1LL * c) % MOD; } } for (int c = 0; c <= N; ++c) { long long val = dp[cf-1][c]; if (c > 0) val = (val + dp[cf-1][c-1]) % MOD; dp[cf][c] = val; } for (int i = cf + 1; i <= N; ++i) { for (int c = 2; c <= i; ++c) { dp[i][c] = (dp[i][c] + dp[i-1][c-1] * 1LL * (c - 2)) % MOD; } for (int c = 0; c < i; ++c) { dp[i][c] = (dp[i][c] + dp[i-1][c+1] * 1LL * c) % MOD; } } cout << dp[N][1] % MOD << '\n'; 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...