Kortit II

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int MOD = 1e9 + 7;
const int MAX_N = 2000;
 
int power(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (1LL * result * base) % MOD;
        }
        base = (1LL * base * base) % MOD;
        exp /= 2;
    }
    return result;
}
 
void precompute_factorials(vector<int>& factorial, vector<int>& inv_factorial, int n) {
    factorial[0] = 1;
    for (int i = 1; i <= n; ++i) {
        factorial[i] = (1LL * factorial[i - 1] * i) % MOD;
    }
    
    inv_factorial[n] = power(factorial[n], MOD - 2);
    for (int i = n - 1; i >= 0; --i) {
        inv_factorial[i] = (1LL * inv_factorial[i + 1] * (i + 1)) % MOD;
    }
}
 
ll dp(int mask, int pos, int a_remaining, int b_remaining, const vector<int>& p1, vector<vector<vector<ll>>>& memo) {
    int n = p1.size();
    
    if (mask == (1 << n) - 1) {
        return (a_remaining == 0 && b_remaining == 0) ? 1 : 0;
    }
    
    if (memo[mask][a_remaining][b_remaining] != -1)
        return memo[mask][a_remaining][b_remaining];
 
    ll res = 0;    
    for (int num = 1; num <= n; num++) {
        int bit = num - 1;
        if (!(mask & (1 << bit))) {
            if (num < p1[pos]) {  
                if (a_remaining > 0)
                    res = (res + dp(mask | (1 << bit), pos + 1, a_remaining - 1, b_remaining, p1, memo)) % MOD;
            } else if (num > p1[pos]) {
                if (b_remaining > 0)
                    res = (res + dp(mask | (1 << bit), pos + 1, a_remaining, b_remaining - 1, p1, memo)) % MOD;
            } else {  
                res = (res + dp(mask | (1 << bit), pos + 1, a_remaining, b_remaining, p1, memo)) % MOD;
            }
        }
    }
 
    return memo[mask][a_remaining][b_remaining] = res;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        int n, a, b;
        cin >> n >> a >> b;
 
        vector<int> factorial(n + 1), inv_factorial(n + 1);
        precompute_factorials(factorial, inv_factorial, n);
 
        vector<int> p1(n);
        for (int i = 0; i < n; i++) {
            p1[i] = i + 1;
        }
 
        
        vector<vector<vector<ll>>> memo(1 << n, vector<vector<ll>>(a + 1, vector<ll>(b + 1, -1LL)));
 
        
        ll answer = dp(0, 0, a, b, p1, memo);
 
        
        cout << (answer * factorial[n]) % MOD << "\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: TIME LIMIT EXCEEDED

Test 4

Group: 4, 5

Verdict: RUNTIME ERROR

Test 5

Group: 5

Verdict: RUNTIME ERROR

Test 6

Group: 5

Verdict: RUNTIME ERROR