oj.uz

Submission #618016

# Submission time Handle Problem Language Result Execution time Memory
618016 2022-08-01T19:13:24 Z chonka Tents (JOI18_tents) C++
100 / 100
 149 ms 94148 KB 
#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.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23508 KB Output is correct
2 Correct 17 ms 23592 KB Output is correct
3 Correct 18 ms 23724 KB Output is correct
4 Correct 19 ms 24412 KB Output is correct
5 Correct 20 ms 23904 KB Output is correct
6 Correct 17 ms 24632 KB Output is correct
7 Correct 17 ms 24020 KB Output is correct
8 Correct 18 ms 24660 KB Output is correct
9 Correct 22 ms 24008 KB Output is correct
10 Correct 18 ms 25024 KB Output is correct
11 Correct 17 ms 23640 KB Output is correct
12 Correct 19 ms 25448 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23508 KB Output is correct
2 Correct 17 ms 23592 KB Output is correct
3 Correct 18 ms 23724 KB Output is correct
4 Correct 19 ms 24412 KB Output is correct
5 Correct 20 ms 23904 KB Output is correct
6 Correct 17 ms 24632 KB Output is correct
7 Correct 17 ms 24020 KB Output is correct
8 Correct 18 ms 24660 KB Output is correct
9 Correct 22 ms 24008 KB Output is correct
10 Correct 18 ms 25024 KB Output is correct
11 Correct 17 ms 23640 KB Output is correct
12 Correct 19 ms 25448 KB Output is correct
13 Correct 16 ms 23548 KB Output is correct
14 Correct 21 ms 32860 KB Output is correct
15 Correct 113 ms 78472 KB Output is correct
16 Correct 20 ms 27316 KB Output is correct
17 Correct 27 ms 36084 KB Output is correct
18 Correct 34 ms 40252 KB Output is correct
19 Correct 149 ms 86276 KB Output is correct
20 Correct 90 ms 74196 KB Output is correct
21 Correct 62 ms 57096 KB Output is correct
22 Correct 67 ms 58752 KB Output is correct
23 Correct 45 ms 50248 KB Output is correct
24 Correct 147 ms 94148 KB Output is correct
25 Correct 109 ms 84516 KB Output is correct
26 Correct 131 ms 89968 KB Output is correct
27 Correct 139 ms 92248 KB Output is correct