Kortit II

input/code.cpp: In function 'll dp(int, int, int, int, const std::vector<int>&, std::vector<std::vector<std::vector<long long int> > >&)':
input/code.cpp:34:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     if (pos == p1.size()) {
      |         ~~~~^~~~~~~~~~~~
input/code.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int num = 1; num <= p1.size(); num++) {
      |                       ~~~~^~~~~~~~~~~~

#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) {
    if (pos == p1.size()) {
        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 <= p1.size(); 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>>(n + 1, vector<ll>(n + 1, -1)));
                
        ll answer = dp(0, 0, a, b, p1, memo);
        
        cout << (answer * factorial[n]) % MOD << endl;
    }
    
    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: RUNTIME ERROR

Test 4

Group: 4, 5

Verdict: RUNTIME ERROR

Test 5

Group: 5

Verdict: RUNTIME ERROR

Test 6

Group: 5

Verdict: RUNTIME ERROR