제출 #769462

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
769462		LucaIlie	Tents (JOI18_tents)	C++17	100 / 100	989 ms	199764 KiB

tents

#include <bits/stdc++.h>

using namespace std;

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

long long dp[MAX_N][MAX_N], fact[MAX_N], comb[MAX_N][MAX_N];

int lgPut( int x, int n ) {
    if ( n == 0 )
        return 1;

    int ans = lgPut( x, n / 2 );
    ans = (long long)ans * ans % MOD;
    if ( n % 2 == 1 )
        ans = (long long)ans * x % MOD;

    return ans;
}

int invers( int x ) {
    return lgPut( x, MOD - 2 );
}

int main() {
    int n, m;

    cin >> n >> m;

    for ( int i = 0; i <= n; i++ )
        dp[i][0] = 1;
    for ( int i = 0; i <= m; i++ )
        dp[0][i] = 1;
    for ( int i = 1; i <= n; i++ ) {
        for ( int j = 1; j <= m; j++ )
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * j * 4) % MOD;
    }

    fact[0] = 1;
    for ( int i = 1; i < MAX_N; i++ )
        fact[i] = fact[i - 1] * i % MOD;
    for ( int i = 0; i < MAX_N; i++ ) {
        comb[i][0] = 1;
        for ( int j = 1; j <= i; j++ )
            comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
    }

    long long sol = 0;
    for ( int a = 0; a <= n; a++ ) {
        for ( int b = 0; b <= m; b++ ) {
            if ( n - a - 2 * b < 0 || m - 2 * a - b < 0 )
                continue;

            long long chooseA = comb[n][a] * comb[m][a] % MOD * comb[m - a][a] % MOD * fact[a] % MOD * fact[a] % MOD * invers( lgPut( 2, a ) ) % MOD;
            long long chooseB = comb[n - a][b] * comb[n - a - b][b] % MOD * comb[m - 2 * a][b] % MOD * fact[b] % MOD * fact[b] % MOD * invers( lgPut( 2, b ) )% MOD;
            sol = (sol + chooseA * chooseB % MOD * dp[n - a - 2 * b][m - 2 * a - b]) % MOD;
        }
    }
    cout << sol - 1;


    return 0;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52