제출 #1367746

#제출 시각아이디문제언어결과실행 시간메모리
1367746yusuf12360캥거루 (CEOI16_kangaroo)C++20
0 / 100
15 ms31880 KiB
#include<bits/stdc++.h>
#define int long long
#define ld long double
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi> 
#define pb push_back
#define fi first
#define se second
#define TII tuple<int, int, int>
#define MT make_tuple
#define mp make_pair
#define ts to_string
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define MIN(x) *min_element(all(x))
#define MAX(x) *max_element(all(x))
#define lb lower_bound
#define ub upper_bound
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2'005, MOD = 1e9 + 7;
int dp[N][N], n, cs, cf;
int s_must_stick, f_must_stick;
void cadd(int &a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
}
int solve() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) dp[i][j] = 0;
    }

    // {
    //     cout << s_must_stick << ' ' << f_must_stick << endl;
    // }

    dp[0][0] = 1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            if(i + 1 == cs) {
                if(s_must_stick) {
                    if(j >= 1) cadd(dp[i + 1][j], dp[i][j]);
                } else cadd(dp[i + 1][j + 1], dp[i][j]);
            } else if(i + 1 == cf) {
                if(f_must_stick) {
                    if(j >= 1) cadd(dp[i + 1][j], dp[i][j]);
                } else cadd(dp[i + 1][j + 1], dp[i][j]);
            } else {
                // new CC
                int slots_to_create = j + 1 - (i > cs) - (i > cf);
                if(slots_to_create > 0) cadd(dp[i + 1][j + 1], dp[i][j] * slots_to_create);

                // merge 2 CCs
                if(j >= 2) cadd(dp[i + 1][j - 1], dp[i][j] * (j - 1) % MOD);
            }
        }
    }

    // {
    //     for(int i = 0; i <= n; i++) {
    //         for(int j = 0; j <= n; j++) cout << dp[i][j] << ' ';
    //         cout << endl;
    //     }
    // }

    return dp[n][1];
}
int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> cs >> cf;
    if(cs > cf) cs = n + 1 - cs, cf = n + 1 - cf;
    
    if(!(n & 1)) f_must_stick = 1;
    int ans = 0;
    cadd(ans, solve());

    // {
    //     cout << ans << endl;
    // }

    s_must_stick = 1; f_must_stick = 1 - f_must_stick;
    cadd(ans, solve());
    cout << ans << '\n';
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…