제출 #1214634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214634		Ghulam_Junaid	NoM (RMI21_nom)	C++20	100 / 100	80 ms	117572 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 4005, mod = 1e9 + 7;
ll n, m, cnt[N], dp[N][N], comb[N][N], f[N], inv[N], prod[N]; // dp[i][j], ways to choose j pairs of places from the first i cnt of mods of m.

ll pwr(ll a, ll b){
    ll res = 1;
    for (; b; b/=2, a = (a * a) % mod) if (b & 1) res = (res * a) % mod;
    return res;
}

int main(){
    f[0] = 1;
    for (ll i = 0; i < N; i ++){
        if (i) inv[i] = pwr(i, mod - 2);
        if (i) f[i] = (f[i - 1] * i) % mod;
        comb[i][0] = comb[i][i] = 1;
        for (ll j = 1; j < i; j ++)
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % mod;
    }

    cin >> n >> m;
    for (ll i = 1; i <= 2 * n; i ++)
        cnt[1 + (i % m)]++;

    prod[2] = 1;
    for (ll i = 4; i < N; i += 2)
        prod[i] = comb[i][2] * prod[i - 2] % mod;

    dp[0][0] = 1;
    for (ll i = 1; i <= m; i ++){
        dp[i][0] = 1;
        for (ll j = 1; j <= n; j ++){
            dp[i][j] = dp[i - 1][j];
            
            for (ll k = 1; k <= j and 2 * k <= cnt[i]; k ++){
                dp[i][j] += (dp[i - 1][j - k] * comb[cnt[i]][2 * k] % mod) * (comb[j][k] * f[2 * k] % mod); 
                dp[i][j] %= mod;
            }
        }
    }

    ll ans = f[2 * n];
    ll last = 0;
    for (ll i = 1; i <= n; i ++){
        // choose pairs, choose places, choose place for each pair, choose for the rest.
        ll val = comb[n][i] * dp[m][i] % mod;
        // val = val * f[i] % mod;
        // val = val * pwr(2, i) % mod;
        val = val * f[2 * n - 2 * i] % mod;
        ll sgn = (i % 2 ? -1 : 1);
        ans += sgn * val;
        ans %= mod;
    }

    cout << (ans + mod) % mod << endl;
}


/*

I have 2k people 
nC2
*
(n - 2)C2
and so on

1 2 3 4 -2
1 2 4 3 -0
1 3 2 4 -0
1 3 4 2 -0
1 4 2 3 -0
1 4 3 2 -2

2 1 3 4 -0
2 1 4 3 -2
2 3 1 4 -0
2 3 4 1 -2
2 4 1 3 -0
2 4 3 1 -0

3 2 1 4 -2
3 2 4 1 -0
3 1 2 4 -0
3 1 4 2 -0
3 4 2 1 -0
3 4 1 2 -2

4 2 3 1 -0
4 2 1 3 -0
4 3 2 1 -2
4 3 1 2 -0
4 1 2 3 -2
4 1 3 2 -0




6 4
138101760

_ _ _ _ _ _ _ _ _ _ _ _

1 : 6C1 * () * f[1]
*/

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 18 / 18
• Subtask 5: 48 / 48