Submission #618016

#	Time	Username	Problem	Language	Result	Execution time	Memory
618016		chonka	Tents (JOI18_tents)	C++98	100 / 100	149 ms	94148 KiB

tents

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7 ;
const int MAXN = 3007 ;

int n , m ;
ll fac[ MAXN ] , inv[ MAXN ] ;

ll fastpow ( ll x , ll pw ) {
    ll ret = 1 ;
    while ( pw > 0 ) {
        if ( ( pw % 2 ) == 0 ) {
            x = ( x * x ) % MOD ;
            pw /= 2 ;
        }
        else {
            ret = ( ret * x ) % MOD ;
            -- pw ;
        }
    }
    return ret ;
}

ll take_single[ MAXN ][ MAXN ] ;
ll cons[ MAXN ][ MAXN ] ;

ll comb ( int up , int down ) {
    if ( up < down || down < 0 ) { return 0 ; }
    ll ret = fac[ up ] ;
    ret = ( ret * inv[ down ] ) % MOD ;
    ret = ( ret * inv[ up - down ] ) % MOD ;
    return ret ;
}

void solve ( ) {
    cin >> n >> m ;
    fac[ 0 ] = 1 ;
    for ( int i = 1 ; i < MAXN ; ++ i ) {
        fac[ i ] = ( fac[ i - 1 ] * i ) % MOD ;
    }
    inv[ MAXN - 1 ] = fastpow ( fac[ MAXN - 1 ] , MOD - 2 ) ;
    for ( int i = MAXN - 2 ; i >= 0 ; -- i ) {
        inv[ i ] = ( inv[ i + 1 ] * ( i + 1 ) ) % MOD ;
    }
    for ( int i = 0 ; i <= n ; ++ i ) {
        take_single[ i ][ 0 ] = 1 ;
    }
    for ( int i = 0 ; i <= m ; ++ i ) {
        take_single[ 0 ][ i ] = 1 ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( int j = 1 ; j <= m ; ++ j ) {
            take_single[ i ][ j ] = ( take_single[ i - 1 ][ j ] + 4 * j * take_single[ i - 1 ][ j - 1 ] ) % MOD ;
        }
    }
    for ( int i = 0 ; i < MAXN ; ++ i ) {
        cons[ 0 ][ i ] = 1 ;
    }
    for ( int cnt = 1 ; cnt < MAXN ; ++ cnt ) {
        for ( int i = 2 * cnt ; i < MAXN ; ++ i ) {
            ll coef = ( 1LL * i * ( i - 1 ) * inv[ 2 ] ) % MOD ;
            cons[ cnt ][ i ] = ( coef * cons[ cnt - 1 ][ i - 2 ] ) % MOD ;
        }
    }
    ll ans = 0 ;
    for ( int i = 0 ; i <= n ; ++ i ) {
        for ( int j = 0 ; j <= m ; ++ j ) {
            int x = n - i - 2 * j , y = m - 2 * i - j ;
            if ( x < 0 || y < 0 ) { continue ; }
            ll aux = comb ( n , i ) ;
            aux = ( aux * cons[ i ][ m ] ) % MOD ;

            aux = ( aux * comb ( m - 2 * i , j ) ) % MOD ;
            aux = ( aux * cons[ j ][ n - i ] ) % MOD ;

            aux = ( aux * take_single[ x ][ y ] ) % MOD ;
            ans = ( ans + aux ) % MOD ;
        }
    }
    cout << ( ans - 1 + MOD ) % MOD << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

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