Kortit II

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const ll ansMod = 1000000007;
 
const int cacheSize = 2002;
ll aCache[cacheSize][cacheSize];
ll binomCache[cacheSize][cacheSize];
 
// a(n+1, r) = r*a(n, r) + (n+1-r)*a(n, r-1) + n*a(n-1, r-1)
ll a(ll n, ll r)
{
    if (r >= n) {
        return 0;
    }
    if (n - 1 == r || r == 1) {
        return 1;
    }
 
    n -= 1;
    ll cacheAns = aCache[n][r];
    if (cacheAns != -1) {
        return cacheAns;
    }
 
    ll ans =((r * a(n, r)) % ansMod)
        + (((n + 1 - r) * a(n, r - 1)) % ansMod)
        + ((n * a(n - 1, r - 1)) % ansMod) % ansMod;
    
    aCache[n][r] = ans;
    return ans;
}
 
ll binomRecursive(ll n, ll k)
{
    if (k > n) {
        return 0;
    }
    if (k == 0 || k == n) {
        return 1;
    }
 
    ll cacheAns = binomCache[n][k];
    if (cacheAns != -1) {
        return cacheAns;
    }
    ll ans = ((binomRecursive(n - 1, k - 1) % ansMod) + (binomRecursive(n - 1, k) % ansMod)) % ansMod;
    binomCache[n][k] = ans;
    return ans;
}
 
ll factorial(ll a)
{
    if (a == 0) {
        return 1;
    }
 
    ll b = a;
    for (int i = 2; i < b; i++) {
        a = a * i % ansMod;
    }
    return a;
}
 
void SolveCase(int cards, int p1, int p2)
{
    int draws = cards - p1 - p2;
 
    string ans1;
    string ans2;
 
    if (p1 + p2 > cards) {
        cout << "0\n";
        return;
    }
 
    if ((p1 > 0 && p2 == 0) || (p2 > 0 && p1 == 0)) {
        cout << "0\n";
        return;
    }
 
    ll ans = binomRecursive(cards, draws);
    //cout << binomRecursive(cards, draws) << "\n";
    ans %= ansMod;
 
    ans *= ans;
    ans %= ansMod;
 
    ans *= factorial(draws);
    //cout << factorial(draws) << "\n";
    ans %= ansMod;
 
    ans *= factorial(p1 + p2);
    //cout << factorial(p1 + p2) << "\n";
    ans %= ansMod;
 
    if (p1 != 0 || p2 != 0) {
        ll bigger = max(p1, p2);
        ll smaller = min(p1, p2);
        ans *= a(bigger + smaller, smaller);
    }
    //cout << p1 << " " << p2 << " " << a(bigger + smaller, smaller) << "\n";
    ans %= ansMod;
 
    cout << ans << "\n";
}
 
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    for (int x = 0; x < cacheSize; x++) {
        for (int y = 0; y < cacheSize; y++) {
            aCache[x][y] = -1;
            binomCache[x][y] = -1;
        }
    }
 
    /*for (int i = 0; i < C; i++) {
        comparison[i] = i + 1;
    }
    int test[C];
    for (int i = 0; i < C; i++) {
        test[i] = 0;
    }
    testBruteForce(test);
    cout << globalCount << "\n";
    cout << playerWinCombinations(g_p1, g_p2) << "\n";
    return 0;*/
    //SolveCase(9, 3, 5);
    //return 0;
 
    int n;
    cin >> n;
    vector<int> input1, input2, input3;
 
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        input1.push_back(a);
        input2.push_back(b);
        input3.push_back(c);
    }
 
    for (int i = 0; i < n; i++) {
        SolveCase(input1[i], input2[i], input3[i]);
    }
}
 
/*
draw possibilities:
cards
draws
 
location combinations of victories and draws:
    (draws)_cards
 
Combinations for draws not placement:
    draws!
 
Combinations for victory positions in list:
    (victories)_p1
 
Combinations for ordering p1 and p2 wins seperately wins:
    p1! * p2!
 
current best: binom(c; d)*binom(c; d)*d!*binom(p1+p2;p1)*p1!*p2!*binom(p1+p2;p1)
better:
binom(c; d)*binom(c; d)*d!*(p1+p2)!*3361*/
 
 
/*const int g_p1 = 7;
const int g_p2 = 4;
const int C = g_p1 + g_p2;
int comparison[C];
int globalCount = 0;
 
// T\left(n{,}k\right)=\sum_{j=0}^n\binom{-j-1}{-n-1}\cdot eulerian1(j{,}k) 
// T\left(n{,}k\right)=\sum_{u=0}^k(-1)^u\cdot\binom{n+1}{u}\cdot(k+1-u)^n 
// T\left(n{,}k\right)=\sum_{j=0}^n\left(\binom{-j-1}{-n-1}\cdot\sum_{u=0}^k\left((-1)^u\cdot\binom{j+1}{u}\cdot(k+1-u)^n\right)\right) 
 
ll factorial(ll a)
{
    if (a == 0) {
        return 1;
    }
 
    ll negative = 1;
    if (a < 0) {
        if (a & 1) {
            negative = -1;
        }
        a *= -1;
    }
 
    ll aCopy = a;
    for (ll i = 1; i < aCopy; i++) {
        a *= i;
    }
    return a * negative;
}
 
ll binomial(ll a, ll b)
{
    if (a < 0) {
        if (b >= 0) {
            return pow(-1, b) * binomial(b - a - 1, b);
        }
        return pow(-1, a - b) * binomial(-b - 1, a - b);
    }
 
    ll a1 = factorial(a);
    ll a2 = factorial(b);
    ll a3 = factorial(a - b);
    //cout << "binom a1 " << a1 << " a2 " << a2 << " a3 " << a3 << "\n";
 
    return a1 / (a2 * a3);
}
 
ll BinomialCoeffient(ll n, ll k)
{
    if (k > n)
        return 0;
 
    ll c = n;
    for (ll i = 1; i < k; i++)
    {
        c *= n - i;
        c /= i + 1;
    }
    return c;
}
 
ll eulerian(ll n, ll k) {
    ll ans = 0;
    for (ll j = 0; j < k + 1; j++) {
        ll loopAns = pow(-1LL, j);
        loopAns *= BinomialCoeffient(n + 1, j) % ansMod;
        loopAns *= pow(k + 1 - j, n);
 
        ans += loopAns;
    }
    return ans;
}
 
ll playerWinCombinations(ll n, ll k)
{
    if (n < 2 || k < 2) {
        return 1;
    }
    n += k - 2;
 
    if (k > n) {
        ll temp = n;
        n = k;
        k = temp;
    }
    n += 2;
 
    ll ans = 0;
    for (ll j = 0; j < n + 1; j++) {
 
        ll E1 = eulerian(j, k);
        E1 *= binomial(-j - 1, -n - 1);
        ans += E1;
        ans %= ansMod;
    }
    return ans;
}
 
bool containsNumber(int numbersUsed[C], int number)
{
    for (int i = 0; i < C; i++) {
        if (numbersUsed[i] == number) {
            return true;
        }
    }
    return false;
}
 
void testBruteForce(int numbersUsed[C])
{
    cout << "called with ";
    for (int i = 0; i < C; i++) {
        cout << numbersUsed[i];
    } 
    cout << "\n";
    bool allUsed = true;
    for (int i = 0; i < C; i++) {
        if (numbersUsed[i] == 0) {
            allUsed = false;
 
            for (int newNum = 1; newNum < C + 1; newNum++) {
                if (comparison[i] != newNum && !containsNumber(numbersUsed, newNum)) {
                    numbersUsed[i] = newNum;
                    testBruteForce(numbersUsed);
                }
            }
            numbersUsed[i] = 0;
            break;
        }
    }
    if (!allUsed) {
        return;
    }
    
    int larger = 0, smaller = 0;
    for (int i = 0; i < C; i++) {
        if (numbersUsed[i] < comparison[i]) {
            smaller++;
        }
        else if (numbersUsed[i] > comparison[i]) {
            larger++;
        }
    }
    if (smaller == g_p1 && larger == g_p2) {
        globalCount++;
    }
}*/
 

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: ACCEPTED