제출 #964083

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

kangaroo

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000;
const int MOD = 1e9 + 7;

struct ZP {
    int x;

    ZP operator + ( ZP a ) {
        return { (x + a.x) % MOD };
    }

    void operator += ( ZP a ) {
        x = (x + a.x) % MOD;
    }

    ZP operator * ( ZP a ) {
        return { (int)((long long)x * a.x % MOD) };
    }

    ZP operator * ( int a ) {
        return { (int)((long long)x * a % MOD) };
    }

    void operator = ( int a ) {
        x = a;
    }

    void out() {
        cout << x << "\n";
    }
};


ZP dp[MAX_N + 1][MAX_N + 1][2][2];

int main() {
    int n, s, f;

    cin >> n >> s >> f;
    if ( s > f )
        swap( s, f );

    if ( s == 1 ) {
        if ( f == 2 )
            dp[3][1][1][1] = 1;
        dp[2][0][1][0] = 1;
    } else
        dp[1][0][0][0] = 1;

    int p = 2;
    for ( int i = 0; i < s - 1; i++ ) {
        for ( int mx = 0; mx <= n; mx++ ) {
            dp[i + 1][mx][0][0] += dp[i][mx][0][0] * (mx * 2 + 2);
            dp[i + 1][mx + 1][0][0] += dp[i][mx][0][0] * (p - 2 - mx * 2);
        }
        if ( i == 0 && s > 1 )
            p--;
        p++;
    }
    for ( int mx = 0; mx <= n; mx++ ) {
        dp[s][mx][0][0] = dp[s - 1][mx][0][0];
        dp[s][mx][0][1] = dp[s - 1][mx][0][1];
        dp[s][mx][1][0] = dp[s - 1][mx][1][0];
        dp[s][mx][1][1] = dp[s - 1][mx][1][1];
    }

    for ( int i = s; i < f - 1; i++ ) {
        for ( int mx = 0; mx <= n; mx++ ) {
            dp[i + 1][mx][0][0] += dp[i][mx][0][0] * (mx * 2 + 1);
            dp[i + 1][mx + 1][0][0] += dp[i][mx][0][0] * (p - 2 - mx * 2);
            dp[i + 1][mx + 1][1][0] += dp[i][mx][0][0];

            dp[i + 1][mx][1][0] += dp[i][mx][1][0] * (mx * 2 + 1);
            dp[i + 1][mx + 1][1][0] += dp[i][mx][1][0] * (p - 1 - mx * 2);
        }
        if ( s == 1 && i == s )
            p--;
        p++;
    }
    for ( int mx = 0; mx <= n; mx++ ) {
        dp[f][mx][0][0] = dp[f - 1][mx][0][0];
        dp[f][mx][0][1] = dp[f - 1][mx][0][1];
        dp[f][mx][1][0] = dp[f - 1][mx][1][0];
        dp[f][mx][1][1] = dp[f - 1][mx][1][1];
    }

    for ( int i = f; i < n; i++ ) {
        for ( int mx = 0; mx <= n; mx++ ) {
            dp[i + 1][mx][0][0] += dp[i][mx][0][0] * mx * 2;
            dp[i + 1][mx + 1][0][0] += dp[i][mx][0][0] * (p - 2 - mx * 2);
            dp[i + 1][mx + 1][1][0] += dp[i][mx][0][0];
            dp[i + 1][mx + 1][0][1] += dp[i][mx][0][0];

            dp[i + 1][mx][1][0] += dp[i][mx][1][0] * mx * 2;
            dp[i + 1][mx + 1][1][0] += dp[i][mx][1][0] * (p - 1 - mx * 2);
            dp[i + 1][mx + 1][1][1] += dp[i][mx][1][0];

            dp[i + 1][mx][0][1] += dp[i][mx][0][1] * mx * 2;
            dp[i + 1][mx + 1][0][1] += dp[i][mx][0][1] * (p - 1 - mx * 2);
            dp[i + 1][mx + 1][1][1] += dp[i][mx][0][1];

            dp[i + 1][mx][1][1] += dp[i][mx][1][1] * mx * 2;
            dp[i + 1][mx + 1][1][1] += dp[i][mx][1][1] * (p - mx * 2);
        }
        if ( f == 2 && i == f )
            p--;
        p++;
    }


    ZP ans;
    if ( n % 2 == 0 )
        ans = dp[n][(n - 2) / 2][0][1] + dp[n][(n - 2) / 2][1][0];
    else
        ans = dp[n][n - 2 - (n - 2) / 2][1][1] + dp[n][(n - 2) / 2][0][0];

    ans.out();

    return 0;
}

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