제출 #1126663

#제출 시각아이디문제언어결과실행 시간메모리
1126663omar123Kangaroo (CEOI16_kangaroo)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h>

using namespace std;
vector<vector<int>> dp;
int n, s, e;
const int mod = 1000000007;
int solve(const int i, const int j){
    if(i == 1) {
        if (j == 1) return 1;
        return 0;
    }
    if(i < 0 || i > n) return 0;
    if(j < 0 || j > n) return 0;

    int &ans = dp[i][j];
    if(ans != -1) return ans;

    if(i == s || i == e) {
        int p1 = solve(i - 1, j - 1); // new components
        int p2 = solve(i - 1, j); // same component
        return ans = (0LL + p1 + p2) % mod;
    }

    if(i > e) {
        int p1 = solve(i - 1, j - 1) * (j - 2LL) % mod;
        int p2 = solve(i - 1, j) * ((j - 2) * 2LL + 2) % mod; 
        int p3 = solve(i - 1, j + 1) * 1LL * j % mod;
        return ans = (0LL + p1 + p2 + p3) % mod;
    }

    if(i > s) {
        int p1 = solve(i - 1, j - 1) * 1LL * (j - 1) % mod; // new component
        int p2 = solve(i - 1, j) * 1LL * ((j - 1) * 2 + 1) % mod; // same component
        int p3 = solve(i - 1, j + 1) * 1LL * j % mod; // merge two components
        return ans = (0LL + p1 + p2 + p3) % mod;
    }

    if(i < s) {
        int p1 = solve(i - 1, j - 1) * 1LL * j % mod; // new component
        int p2 = solve(i - 1, j) * 1LL * (2 * j) % mod; // same component
        int p3 = solve(i - 1, j + 1) * 1LL * j % mod; // merge two components
        return ans = (0LL + p1 + p2 + p3) % mod;
    }

    assert(false);
    return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // freopen("kangaroo.in", "r", stdin);
    // freopen("kangaroo.out", "w", stdout);

    
    while(cin >> n >> s >> e) {
        dp = vector<vector<int>> (n + 1, vector<int>(n + 1, -1));
        if(s > e) swap(s, e);
        cout << solve(n, n) << '\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...