제출 #1118303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118303		vjudge1	캥거루 (CEOI16_kangaroo)	C++17	100 / 100	35 ms	23132 KiB

kangaroo

#include "bits/stdc++.h"

using ll = long long;
using namespace std;

const int md = 1000000007;
const int mxN = 2003;

ll dp[mxN][mxN];

int main() {
    int N, cs, cf;
    cin >> N >> cs >> cf;

    dp[1][1] = 1;
    int fixed = 0;
    for (int i = 1; i <= N; i ++) {
        if (i == cs) {
            fixed ++;
        }
        if (i == cf) {
            fixed ++;
        }
        if (i ^ 1) {
            for (int j = 1; j <= i; j ++) {
                if (i ^ cs && i ^ cf) {
                    (dp[i][j] += dp[i - 1][j - 1] * (j - fixed) % md) %= md;
                    (dp[i][j] += dp[i - 1][j + 1] * j % md) %= md;
                } else {
                    (dp[i][j] += dp[i - 1][j - 1]) %= md;
                    (dp[i][j] += dp[i - 1][j]) %= md;
                }
            }
        }
    }
    cout << dp[N][1] << endl;
}

/*

1       36275                      4

3        1    2

yeni component
elementi kimese birlesdirirsen
ya da iki componenti merge edirsen

*/

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49