제출 #964063

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

kangaroo

#include <bits/stdc++.h>

using namespace std;

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

struct ZP {
    int x;
};


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

void afis( int n, int i ) {
    for ( int mn = 0; mn <= n; mn++ ) {
        for ( int mx = 0; mx <= n; mx++ )
            printf( "%d: %d %d -- %d %d %d %d\n", i, mn, mx, dp[i][mn][mx][0][0], dp[i][mn][mx][0][1], dp[i][mn][mx][1][0], dp[i][mn][mx][1][1] );
    }
}

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

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

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

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

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

                printf( "%d %d %d %d\n", i, mn, mx, dp[3][1][1][1][0] );
                dp[i + 1][mn][mx][1][0] += dp[i][mn][mx][1][0] * (mx * 2 + 1);
                dp[i + 1][mn + 1][mx + 1][1][0] += dp[i][mn][mx][1][0] * (p - 1 - mx * 2);
            }
        }
        if ( s == 1 && i == s )
            p--;
        p++;
    }
    for ( int mn = 0; mn <= n; mn++ ) {
        for ( int mx = 0; mx <= n; mx++ ) {
            dp[f][mn][mx][0][0] = dp[f - 1][mn][mx][0][0];
            dp[f][mn][mx][0][1] = dp[f - 1][mn][mx][0][1];
            dp[f][mn][mx][1][0] = dp[f - 1][mn][mx][1][0];
            dp[f][mn][mx][1][1] = dp[f - 1][mn][mx][1][1];
        }
    }

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

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

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

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

    int ans = 0;
    for ( int i = 0; i < 2; i++ ) {
        for ( int j = 0; j < 2; j++ ) {
            if ( n % 2 == 0 )
                ans += dp[n][(n - 2) / 2][(n - 2) / 2][i][j];
            else
                ans += dp[n][(n - 2) / 2][n - (n - 2) / 2][i][j] + dp[n][n - (n - 2) / 2][(n - 2) / 2][i][j];
        }
    }

    cout << ans;

    return 0;
}

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