제출 #769462

#제출 시각아이디문제언어결과실행 시간메모리
769462LucaIlieTents (JOI18_tents)C++17
100 / 100
989 ms199764 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...