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> f;

void prep() {
    f.resize(MAXN);
    f[0] = 1;
    for(int i = 1; i < MAXN; i++) {
        f[i] = (f[i-1] * i) % MOD;
    }
}

long long comb(int tot, int sel) {
    if(sel > tot) return 0;
    if(sel == 0 || sel == tot) return 1;
    if(sel > tot/2) sel = tot-sel;
    
    vector<long long> p(sel + 1, 0);
    p[0] = 1;
    
    for(int x = 1; x <= tot; x++) {
        for(int y = min(x, sel); y > 0; y--) {
            p[y] = (p[y] + p[y-1]) % MOD;
        }
    }
    return p[sel];
}

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 > MAXN) return 0;
    
    if(down > up) swap(down, up);
    if(dp[down][up] != -1) return dp[down][up];
    
    long long ans = 0;
    long long tot = down + up;
    
    if(tot > 1) {
        ans = (((tot - 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 = comb(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);
    
    prep();
    
    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) * f[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: TIME LIMIT EXCEEDED