Kortit II

#include <iostream>
 
using namespace std;
 
const int MAX_N = 2000;
const long long MOD = 1000000007;
 
long long F[MAX_N + 1]{};
long long A[MAX_N + 1][MAX_N + 1]{};
long long C[MAX_N + 1][MAX_N + 1]{};
long long D[MAX_N + 1][MAX_N + 1]{};
 
long long compute_factorial(int n)
{
    if (n == 0)
        return 1;
 
    if (F[n] != 0)
        return F[n];
 
    F[n] = n * compute_factorial(n - 1) % MOD;
 
    return F[n];
}
 
long long compute_eulerian_number(int n, int k)
{
    if (n == k)
        return 0;
 
    if (A[n][k] != 0)
        return A[n][k];
 
    if (k >= n - k)
        k = n - k - 1;
 
    if (k == 0)
        return 1;
 
    A[n][k] = ((n - k) * compute_eulerian_number(n - 1, k - 1) % MOD +
               (k + 1) * compute_eulerian_number(n - 1, k) % MOD) %
              MOD;
    A[n][n - k - 1] = A[n][k];
 
    return A[n][k];
}
 
long long compute_binomial_coefficient(int n, int k)
{
    if (k == 0 || k == n)
        return 1;
 
    if (C[n][k] != 0)
        return C[n][k];
 
    if (k > n - k)
        k = n - k;
 
    C[n][k] = (compute_binomial_coefficient(n - 1, k - 1) +
               compute_binomial_coefficient(n - 1, k)) %
              MOD;
    C[n][n - k] = C[n][k];
 
    return C[n][k];
}
 
long long compute_derangement(int n, int k)
{
    if (D[n][k] != 0)
        return D[n][k];
 
    if (k > n - k)
        k = n - k;
 
    long long sum = 0;
    for (int j = 0; j < n - k; j++)
    {
        long long binomial = compute_binomial_coefficient(n, j);
        long long eulerian = compute_eulerian_number(n - j, k);
        long long item = binomial * eulerian % MOD;
        item = j % 2 == 0 ? item : MOD - item;
        sum += item;
        sum %= MOD;
    }
    D[n][k] = D[n][n - k] = sum;
 
    return sum;
}
 
int main()
{
    int t;
    cin >> t;
 
    while (t--)
    {
        int n, a, b;
        cin >> n >> a >> b;
 
        if ((a != 0 && b == 0) || (a == 0 && b != 0) || (a + b > n))
        {
            cout << 0 << endl;
            continue;
        }
 
        int tie = n - a - b;
 
        long long n_derangement = compute_derangement(n - tie, b);
        long long n_factorial = compute_factorial(n);
        long long n_tie_binomial = compute_binomial_coefficient(n, tie);
        long long result = n_derangement *
                           n_factorial % MOD *
                           n_tie_binomial % MOD;
 
        cout << result << endl;
    }
 
    return 0;
}

Test 1

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 2

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 4, 5

Verdict: WRONG ANSWER

Test 5

Group: 5

Verdict: ACCEPTED

Test 6

Group: 5

Verdict: ACCEPTED