Kortit II

#include <vector>
#include <iostream>
#include <unordered_map>
 
using namespace std;
 
const int mod = 1e9 + 7;
 
int factorial(int n) {
    long long total = 1;
    while (n > 1) {
        total = (total * n) % mod;
        n--;
    }
    return total;
}
 
unordered_map<long long, int> memo;
 
long long state_key(int round, int wins_a, int wins_b, int ties, int bitmask) {
    return ((long long)round << 40) | ((long long)wins_a << 30) | ((long long)wins_b << 20) | ((long long)ties << 10) | bitmask;
}
 
 
int dp(int round, int n, int a, int b, int t, int wins_a, int wins_b, int ties, int bitmask) {
    if (round > n) {
        return (wins_a == a && wins_b == b && ties == t) ? factorial(n) : 0;
    }
 
    long long key = state_key(round, wins_a, wins_b, ties, bitmask);
    if (memo.count(key)) return memo[key];
 
    int total_ways = 0;
    for (int card = 1; card <= n; ++card) {
        if (bitmask & (1 << (card - 1))) {
            int new_bitmask = bitmask & ~(1 << (card - 1));
 
            if (card > round) {
                if (wins_a + 1 <= a) {
                    total_ways = (total_ways + dp(round + 1, n, a, b, t, wins_a + 1, wins_b, ties, new_bitmask)) % mod;
                }
            } else if (card < round) {
                if (wins_b + 1 <= b) {
                    total_ways = (total_ways + dp(round + 1, n, a, b, t, wins_a, wins_b + 1, ties, new_bitmask)) % mod;
                }
            } else {
                if (ties + 1 <= t) {
                    total_ways = (total_ways + dp(round + 1, n, a, b, t, wins_a, wins_b, ties + 1, new_bitmask)) % mod;
                }
            }
        }
    }
 
    return memo[key] = total_ways;
}
 
 
int gameresults(int n, int a, int b) {
    memo.clear();
    int t = n - a - b;
    if (t < 0 || a > n || b > n) {
        return 0;
    }
 
 
    int fullbitmask = (1 << n) - 1;
    return dp(1, n, a, b, t, 0, 0, 0, fullbitmask);
}
 
int main() {
    int test_cases;
    cin >> test_cases;
 
    vector<int> results(test_cases);
    for (int i = 0; i < test_cases; ++i) {
        int n, a, b;
        cin >> n >> a >> b;
        results[i] = gameresults(n, a, b);
    }
 
    for (int result : results) {
        cout << result << 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: TIME LIMIT EXCEEDED

Test 4

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 5

Verdict: TIME LIMIT EXCEEDED