Kortit II

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 2001;
vector<vector<long long>> dp(MAXN, vector<long long>(MAXN, -1));
vector<long long> fac;
vector<vector<long long>> C;

void precompute() {
    fac.resize(MAXN);
    fac[0] = 1;
    for(int i = 1; i < MAXN; i++) {
        fac[i] = (fac[i-1] * i) % MOD;
    }
    
    C.resize(MAXN, vector<long long>(MAXN));
    for(int i = 0; i < MAXN; i++) {
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
}

long long solve_rec(int down, int up) {
    if(down < 0 || up < 0) return 0;
    if(down == 0 && up == 0) return 1;
    if(down + up <= 1) return 0;
    
    if(down > up) swap(down, up);
    
    if(dp[down][up] != -1) return dp[down][up];
    
    long long ans = 0;
    long long total = down + up;
    
    if(total > 1) {
        ans = (((total - 1) * solve_rec(down - 1, up - 1)) % MOD);
    }
    
    if(down > 0) {
        ans = (ans + ((long long)down * solve_rec(down, up - 1)) % MOD) % MOD;
    }
    
    if(up > 0) {
        ans = (ans + ((long long)up * solve_rec(down - 1, up)) % MOD) % MOD;
    }
    
    return dp[down][up] = ans;
}

long long calc(int len, int same, int up, int down) {
    if(same + up + down != len || len <= 0 || same < 0 || up < 0 || down < 0) return 0;
    if(up + down > len || same > len) return 0;
    
    long long p1 = C[len][same];
    if(p1 == 0) return 0;
    
    long long p2 = solve_rec(down, up);
    if(p2 == 0) return 0;
    
    return (p1 * p2) % MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    precompute();
    
    int q;
    cin >> q;
    
    while(q--) {
        int n, up, down;
        cin >> n >> up >> down;
        
        if(up + down > n) {
            cout << "0\n";
            continue;
        }
        
        int same = n - up - down;
        long long ans = (calc(n, same, up, down) * fac[n]) % MOD;
        cout << ans << "\n";
    }
    
    return 0;
}

Test 1

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Group: 3, 4, 5

Verdict: ACCEPTED

Test 4

Group: 4, 5

Verdict: ACCEPTED

Test 5

Group: 5

Verdict: ACCEPTED

Test 6

Group: 5

Verdict: ACCEPTED