Submission #364698

#	Time	Username	Problem	Language	Result	Execution time	Memory
364698		Nima_Naderi	Tents (JOI18_tents)	C++14	100 / 100	284 ms	71472 KiB

tents

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 3e3 + 10;
const ll Mod = 1e9 + 7;
ll power(ll a, ll b){
    return (!b ? 1 : power(a * a % Mod, b / 2) * (b & 1LL ? a : 1) % Mod);
}
ll inv(ll x){
    return power(x, Mod - 2);
}
inline void mkay(ll& x){
    while(x >= Mod) x -= Mod;
}
ll n, m;
ll dp[MXN][MXN], F[MXN], I[MXN];
ll nCr(ll n, ll r){
    if(r < 0 || r > n) return 0;
    return F[n] * I[r] % Mod * I[n - r] % Mod;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    F[0] = I[0] = 1;
    for(int i = 1; i < MXN; i ++) F[i] = F[i - 1] * i % Mod;
    I[MXN - 1] = inv(F[MXN - 1]);
    for(int i = MXN - 2; i; i --) I[i] = I[i + 1] * (i + 1) % Mod;
    for(int i = 0; i < MXN; i ++) dp[i][0] = dp[0][i] = 1;
    dp[1][1] = 4 + 1;
    for(int j = 2; j < MXN; j ++){
        dp[j][1] = dp[1][j] = (4 * j + nCr(j, 2) + 1) % Mod;
    }
    for(int i = 2; i < MXN; i ++){
        for(int j = 2; j < MXN; j ++){
            dp[i][j] = (dp[i - 1][j] + nCr(j, 2) * dp[i - 1][j - 2] % Mod);
            dp[i][j] = (dp[i][j] + j * 4 * dp[i - 1][j - 1] % Mod);
            dp[i][j] = (dp[i][j] + j * (i - 1) % Mod * dp[i - 2][j - 1] % Mod);
            mkay(dp[i][j]);
        }
    }
    cin >> n >> m;
    cout << dp[n][m] - 1 << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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