Kortit II

#include <bits/stdc++.h>
#define ln "\n"
using namespace std;
using ll = long long;
int MOD = 1e9+7;
 
ll modExp(ll base, ll exp, int mod) {
    ll result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}
 
ll getMul(ll a, ll b) {
    ll n = a + b;
    if(n > 8) {
        vector<vector<ll>> dpv(20, vector<ll> (20,0));
        if(b > a) swap(a,b);
        // 20
        dpv[19][1] = 1;
        dpv[18][2] = 1048535;
        dpv[17][3] = 454279324;
        dpv[16][4] = 523632634;
        dpv[15][5] = 385470287;
        dpv[14][6] = 871449594;
        dpv[13][7] = 530109088;
        dpv[12][8] = 285082030;
        dpv[11][9] = 65680015;
        dpv[10][10] = 694296779;
        // 19
        dpv[18][1] = 1;
        dpv[17][2] = 524249;
        dpv[16][3] = 146795686;
        dpv[15][4] = 488340185;
        dpv[14][5] = 113217428;
        dpv[13][6] = 143784997;
        dpv[12][7] = 897051207;
        dpv[11][8] = 405967908;
        dpv[10][9] = 427513351;
        // 18
        dpv[17][1] = 1;
        dpv[16][2] = 262107;
        dpv[15][3] = 380081105;
        dpv[14][4] = 131277918;
        dpv[13][5] = 653878722;
        dpv[12][6] = 283239251;
        dpv[11][7] = 224880232;
        dpv[10][8] = 776442791;
        dpv[9][9] = 744422627;
        // 17
        dpv[16][1] = 1;
        dpv[15][2] = 131037;
        dpv[14][3] = 125667333;
        dpv[13][4] = 166996279;
        dpv[12][5] = 496884791;
        dpv[11][6] = 51334367;
        dpv[10][7] = 873374622;
        dpv[9][8] = 331293441;
        // 16
        dpv[15][1] = 1;
        dpv[14][2] = 65503;
        dpv[13][3] = 41408833;
        dpv[12][4] = 352853130;
        dpv[11][5] = 353683273;
        dpv[10][6] = 443916467;
        dpv[9][7] = 23079360;
        dpv[8][8] = 634184753;
        // 15
        dpv[14][1] = 1;
        dpv[13][2] = 32737;
        dpv[12][3] = 13579309;
        dpv[11][4] = 780889437;
        dpv[10][5] = 218582477;
        dpv[9][6] = 767040909;
        dpv[8][7] = 753131331;
        // 14
        dpv[13][1] = 1;
        dpv[12][2] = 16355;
        dpv[11][3] = 4422913;
        dpv[10][4] = 178065811;
        dpv[9][5] = 977056426;
        dpv[8][6] = 789852802;
        dpv[7][7] = 172272237;
        // 13
        dpv[12][1] = 1;
        dpv[11][2] = 8165;
        dpv[10][3] = 1426725;
        dpv[9][4] = 39474449;
        dpv[8][5] = 302458313;
        dpv[7][6] = 802028813;
        // 12
        dpv[11][1] = 1;
        dpv[10][2] = 4071;
        dpv[9][3] = 453905;
        dpv[8][4] = 8422679;
        dpv[7][5] = 42924113;
        dpv[6][6] = 72605303;
        // 11
        dpv[10][1] = 1;
        dpv[9][2] = 2025;
        dpv[8][3] = 141549;
        dpv[7][4] = 1704693;
        dpv[6][5] = 5494017;
        // 10
        dpv[9][1] = 1;
        dpv[8][2] = 1003;
        dpv[7][3] = 42865;
        dpv[6][4] = 320107;
        dpv[5][5] = 607009;
        // 9
        dpv[8][1] = 1;
        dpv[7][2] = 493;
        dpv[6][3] = 12421;
        dpv[5][4] = 53833;
        return dpv[a][b];
    } else {
        ll limit = (1LL << n), maxState = (a + 1) * (b + 1);
        
        vector<vector<ll>> dp(limit, vector<ll>(maxState, 0));
        dp[0][0] = 1;
 
        for (int mask = 0; mask < limit; mask++) {
            int winCount = __builtin_popcount(mask);
 
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) continue;
                int num = i + 1;
                for (int state = 0; state < maxState; state++) {
                    if (dp[mask][state] == 0) continue;
                    ll w = state / (b + 1);
                    ll l = state % (b + 1);
                    if (num > winCount + 1 && w + 1 <= a) {
                        ll newState = (w + 1) * (b + 1) + l;
                        dp[mask | (1 << i)][newState] = (dp[mask | (1 << i)][newState] + dp[mask][state]) % MOD;
                    } else if (num < winCount + 1 && l + 1 <= b) {
                        ll newState = w * (b + 1) + (l + 1);
                        dp[mask | (1 << i)][newState] = (dp[mask | (1 << i)][newState] + dp[mask][state]) % MOD;
                    }
                }
            }
        }
        
        ll totalWays = 0;
        int target = a * (b + 1) + b;
        for (int mask = 0; mask < limit; mask++) {
            totalWays = (totalWays + dp[mask][target]) % MOD;
        }
        return totalWays;
    }
}
 
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 << ln;
        } else {
            ll variations = getMul(a, b);
            ll c = a + b;
 
            ll finalMul = 1;
            for (ll i = 1; i <= c; i++) {
                finalMul = (finalMul * i) % MOD;
            }
 
            for (ll i = c + 1; i <= n; i++) {
                finalMul = (finalMul * i) % MOD;
                finalMul = (finalMul * i) % MOD;
            }
 
            ll diver = 1;
            for (ll j = 1; j <= (n - c); j++) {
                diver = (diver * j) % MOD;
            }
            ll diverInv = modExp(diver, MOD - 2, MOD);  
            
            finalMul = (finalMul * variations) % MOD;
            finalMul = (finalMul * diverInv) % MOD;
 
            cout << finalMul << ln;
        }
    }
}

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: RUNTIME ERROR

Test 5

Group: 5

Verdict: RUNTIME ERROR

Test 6

Group: 5

Verdict: RUNTIME ERROR