제출 #832463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832463		Ahmed_Salah7	캥거루 (CEOI16_kangaroo)	C++17	6 / 100	7 ms	16084 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2000 + 10, M = 1e6 + 6, mod = 1e9 + 7;

int n;
int dp[N][N];

int add(int a, int b) {
    return (a + b) % mod;
}

int mul(int a, int b) {
    return (1LL * a * b) % mod;
}

int s, e;

int sol(int i, int j) {
    if (i == n)
        return (j == 1);
    int &ret = dp[i][j];
    if (~ret)
        return ret;
    ret = 0;
    if (i + 1 == s) {
        if (j)ret = sol(i + 1, j); // add to the first comp
        ret = add(ret, sol(i + 1, j + 1)); // create new comp
        return ret;
    }
    if (i + 1 == e) {
        if (j)ret = sol(i + 1, j); // add to the last comp
        ret = add(ret, sol(i + 1, j + 1)); // create new comp
        return ret;
    }
    // add newComp
    ret = mul(sol(i + 1, j + 1), (j + 1 - (i + 1 > s) + (i + 1 > e)));
    // merge twoComps
    if (j)
        ret = add(ret, mul(sol(i + 1, j - 1), (j - 1)));
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(dp, -1, sizeof dp);
    cin >> n >> s >> e;
    cout << sol(0, 0);
}

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