Kortit II

#include <iostream>
#include <vector>
using namespace std;
 
const int MOD = 1e9 + 7;
 
int fact(int val) {
    long long res = 1;
    while (val > 1) {
        res = (res * val) % MOD;
        val--;
    }
    return res;
}
 
long long comb(int tot, int sel) {
    if (sel > tot) return 0;
    if (sel == 0 || sel == tot) return 1;
    
    vector<long long> dp(sel + 1, 0);
    dp[0] = 1;
    
    for (int x = 1; x <= tot; x++) {
        for (int y = min(x, sel); y > 0; y--) {
            dp[y] = (dp[y] + dp[y-1]) % MOD;
        }
    }
    return dp[sel];
}
 
long long solve_rec(int down, int up, vector<vector<long long>>& dp) {
    if (down < 0 || up < 0) return 0;
    if (down == 0 && up == 0) return 1;
    if (down + up <= 1) return 0;
    
    if (dp[down][up] != -1) return dp[down][up];
    
    long long ans = 0;
    ans = (((long long)(down + up - 1) * solve_rec(down - 1, up - 1, dp)) % MOD);
    ans = (ans + ((long long)down * solve_rec(down, up - 1, dp)) % MOD) % MOD;
    ans = (ans + ((long long)up * solve_rec(down - 1, up, dp)) % MOD) % MOD;
    
    return dp[down][up] = ans;
}
 
long long calc(int len, int same, int up, int down) {
    if (same + up + down != len) return 0;
    if (len <= 0 || same < 0 || up < 0 || down < 0) return 0;
    
    vector<vector<long long>> dp(len + 1, vector<long long>(len + 1, -1));
    
    long long p1 = comb(len, same);
    long long p2 = solve_rec(down, up, dp);
    
    return (p1 * p2) % MOD;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int q;
    cin >> q;
    
    while (q--) {
        int n, up, down;
        cin >> n >> up >> down;
        int same = n - up - down;
        
        long long ans = (calc(n, same, up, down) * fact(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: TIME LIMIT EXCEEDED

Test 6

Group: 5

Verdict: TIME LIMIT EXCEEDED