oj.uz

Submission #769461

# Submission time Handle Problem Language Result Execution time Memory
769461 2023-06-29T15:32:49 Z LucaIlie Tents (JOI18_tents) C++17
0 / 100
 55 ms 118000 KB 
#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] * comb[m - a][a] * fact[a] * fact[a] * invers( lgPut( 2, a ) ) % MOD;
            long long chooseB = comb[n - a][b] * comb[n - a - b][b] * comb[m - 2 * a][b] * fact[b] * fact[b] * 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
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 117192 KB Output is correct
2 Correct 53 ms 117116 KB Output is correct
3 Correct 55 ms 117340 KB Output is correct
4 Correct 53 ms 118000 KB Output is correct
5 Incorrect 53 ms 117572 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 117192 KB Output is correct
2 Correct 53 ms 117116 KB Output is correct
3 Correct 55 ms 117340 KB Output is correct
4 Correct 53 ms 118000 KB Output is correct
5 Incorrect 53 ms 117572 KB Output isn't correct
6 Halted 0 ms 0 KB -