Kortit II

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
 
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
// const ll M = 998244353;
const ll M = 1e9 + 7;
// ll M;
 
 
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define PI 3.141592653589793238462643383279502884L
 
const ll INFL = 1e18;
const int INF = 1e9;
const ll maxN = 5e5+1;
 
ll inv(ll a) {
    return a<=1 ? a: M - (ll)(M/a) * inv(M%a) % M;
}
 
ll modpow(ll a, ll b) {
    a %= M;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % M;
        a = a * a % M;
        b >>= 1;
    }
    return res;
}
 
ll fact[maxN];
ll inv_fact[maxN];
ll t[100][100];
 
void calc_fact() {
    fact[0] = 1;
    for (int i=1; i<maxN; i++) {
        fact[i] = fact[i-1]*i % M;
        inv_fact[i] = inv(fact[i]);
    }
}
 
ll nCr(int n, int k) {
    return fact[n] * inv(fact[k]*fact[n-k] % M) % M;
}
 
 
ll dp2[2001][2001];
 
ll get(ll n, ll a, ll b) {
    if (a==0 && b==0) return 1;
    if (a+b>n) return 0;
    // return dp[n][a][b];
    return nCr(n, n-(a+b))*dp2[a+b][a]%M;
}
 
void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    cout << get(n, a, b)*fact[n]%M << '\n';
    // cout << ans*fact[n]%M << '\n'; 
 
    
}
int main() {
    calc_fact();
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    // cout << setprecision(12);
    // for (ll n=1; n<=100; n++) {
    //     dp[n][0][0] = 1;
    //     for (ll a=1; a<=n; a++) {
    //         for (ll b=1; b<=n; b++) {
    //             if (a+b>n) continue;
    //             dp[n][a][b] = dp[n-1][a][b];
    //             dp[n][a][b] += (n-a-b+1)*(dp[n-1][a-1][b-1]);
    //             dp[n][a][b] += a*dp[n-1][a][b-1];
    //             dp[n][a][b] += b*dp[n-1][a-1][b];
    //             dp[n][a][b] %= M;
    //             assert(nCr(n, n-(a+b))*dp[a+b][a][b]%M==dp[n][a][b]);
    //         }
    //     }
    //
    // }
    for (ll n=1; n<=2000; n++) {
        for (ll a=1; a<n; a++) {
            ll b = n-a;
            dp2[n][a] = get(n-1,a,b);
            dp2[n][a] += (n-a-b+1)*get(n-1,a-1, b-1);
            dp2[n][a] += a*get(n-1,a,b-1);
            dp2[n][a] += b*get(n-1,a-1,b);
            dp2[n][a] %= M;
            // cout << n << ' ' << a << ' ' << b << endl;
            // cout << dp2[n][a] << ' ' << dp[n][a][b] << endl;
            // cout << endl;
            // assert(dp2[n][a]==dp[n][a][b]);
        }
 
    }
 
 
    int tc = 1;
    cin >>tc;
    while (tc--) solve();
 
}
 

Test 1

Group: 1, 2, 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 2, 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

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