Submission #610122

#	Time	Username	Problem	Language	Result	Execution time	Memory
610122		czhang2718	Tents (JOI18_tents)	C++17	100 / 100	89 ms	70728 KiB

tents

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
#define int ll

const int N=3001, mod=1e9+7;
int n, m;
// int C[N][N];
// int f[N][N];
int dp[N][N];

signed main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    // a left, b right
    // nCa * mCb * (m chooose 2a) * (2a)!/2^a * (n choose 2b) * (2b)!/2^b * f(n-a-2*b,m-2*a-b)
    // f(a,b) =  f(a-1,b) + b*f(a-1,b-1)

    // for(int i=0; i<N; i++) C[i][0]=1;
    // for(int i=1; i<N; i++){
    //     for(int j=1; j<=i; j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
    // }

    for(int i=0; i<=max(n,m); i++) dp[i][0]=dp[0][i]=1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            dp[i][j]=(i>=2?i*(i-1)/2*dp[i-2][j-1]:0)+i*4*dp[i-1][j-1]+dp[i][j-1]+(j>=2?(j-1)*i*dp[i-1][j-2]:0);
            dp[i][j]%=mod;
        }
    }
    cout << (dp[n][m]+mod-1)%mod;
}

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