Kortit II

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
/*
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 ll ansMod = 1000000007;
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 eulerian(ll n, ll k) {
    ll ans = 0;
    for (ll j = 0; j < k + 1; j++) {
        ll loopAns = pow(-1, j);
        loopAns *= binomial(n + 1, j);
        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;
    }
    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++;
    }
}
 
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 = binomial(cards, draws);
    ans *= ans;
    ans *= factorial(draws);
    ans *= factorial(p1 + p2);
    ans *= playerWinCombinations(p1, p2);

    /*cout << binomial(cards, draws) << "\n";
    cout << factorial(draws) << "\n";
    cout << factorial(p1 + p2) << "\n";
    cout << playerWinCombinations(p1, p2) << "\n";*/
    
    cout << ans % ansMod << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    /*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]);
    }
}

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: WRONG ANSWER

Test 4

Group: 4, 5

Verdict: RUNTIME ERROR

Test 5

Group: 5

Verdict: RUNTIME ERROR

Test 6

Group: 5

Verdict: RUNTIME ERROR