Submission #1219233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219233		arbuzick	NoM (RMI21_nom)	C++20	100 / 100	113 ms	16220 KiB

Main

#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = 1e9 + 7;

int binpow(int n, int k) {
    int ans = 1;
    while (k) {
        if (k & 1) {
            ans = ans * 1LL * n % MOD;
        }
        n = n * 1LL * n % MOD;
        k >>= 1;
    }
    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> sz(m);
    for (int i = 0; i < n * 2; ++i) {
        sz[i % m]++;
    }
    vector<int> f(n * 2 + 1), _f(n * 2 + 1);
    f[0] = _f[0] = 1;
    for (int i = 1; i <= n * 2; ++i) {
        f[i] = f[i - 1] * 1LL * i % MOD;
        _f[i] = binpow(f[i], MOD - 2);
    }
    auto c = [&](int n, int k) -> int {
        return f[n] * 1LL * _f[k] % MOD * _f[n - k] % MOD;
    };
    vector<int> dp(n + 1);
    vector<vector<int>> dp_nw(m + 1, vector<int>(n + 1));
    dp_nw[0][0] = 1;
    for (int i = 0; i < m; ++i) {
        for (int cnt_prv = 0; cnt_prv <= n; ++cnt_prv) {
            for (int add = 0; cnt_prv + add <= n && add * 2 <= sz[i]; ++add) {
                dp_nw[i + 1][cnt_prv + add] += dp_nw[i][cnt_prv] * 1LL * c(sz[i], add * 2) % MOD * f[add * 2] % MOD * c(n - cnt_prv, add) % MOD;
                if (dp_nw[i + 1][cnt_prv + add] >= MOD) {
                    dp_nw[i + 1][cnt_prv + add] -= MOD;
                }
            }
        }
    }
    for (int cnt = n; cnt >= 0; --cnt) {
        dp[cnt] = dp_nw[m][cnt];
        dp[cnt] = dp[cnt] * 1LL * f[n * 2 - cnt * 2] % MOD;
        for (int cnt2 = cnt + 1; cnt2 <= n; ++cnt2) {
            dp[cnt] = (dp[cnt] - (dp[cnt2] * 1LL * c(cnt2, cnt) % MOD) + MOD) % MOD;
        }
    }
    cout << dp[0] << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

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