Submission #503707

#	Time	Username	Problem	Language	Result	Execution time	Memory
503707		Stickfish	NoM (RMI21_nom)	C++17	34 / 100	726 ms	5716 KiB

Main

#include <iostream>
using namespace std;
using ll = long long;

const ll MOD = 1000000007;
const ll MAXN = 2077;

ll pw(ll a, ll m) {
    if (!m)
        return 1;
    a %= MOD;
    if (m % 2)
        return a * pw(a, m - 1) % MOD;
    return pw(a * a, m / 2);
}

ll fact[MAXN * 2];
ll rfact[MAXN * 2];

ll choose(ll n, ll k) {
    if (n < 0 || k < 0 || k > n)
        return 0;
    return (fact[n] * rfact[k] % MOD) * rfact[n - k] % MOD;
}

ll dp[MAXN][MAXN];

signed main() {
    fact[0] = rfact[0] = 1;
    for (int i = 1; i < MAXN * 2; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
        rfact[i] = pw(fact[i], MOD - 2);
    }
    int n, m;
    cin >> n >> m;
    //if (m == 1) {
        //cout << 0 << endl;
        //return 0;
    //}
    int sz = 2 * n / m;
    int szinc = 2 * n % m;
    int smsz = sz + int(0 < szinc);
    dp[0][0] = (choose(n, smsz) * fact[smsz]) % MOD;
    //cout << dp[0][0] << endl;
    for (int i = 1; i < m; ++i) {
        int szi = sz + int(i < szinc);
        for (int c = 0; c <= n; ++c) {
            for (int cp = 0; cp <= c; ++cp) {
                ll cnt1 = smsz - cp * 2;
                ll cnt0 = n - cp - cnt1;
                //if (cnt1 < 0 || cnt0 < 0)
                    //continue;
                dp[i][c] += (dp[i - 1][cp] * choose(cnt1, c - cp) % MOD) * choose(cnt0, szi - (c - cp));
                dp[i][c] %= MOD;
            }
            dp[i][c] *= fact[szi];
            dp[i][c] %= MOD;
            //cout << dp[i][c] << ' ';
        }
        smsz += szi;
        //cout << endl;
    }
    cout << dp[m - 1][n] * pw(2, n) % MOD << endl;
}

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