Submission #503708

#	Time	Username	Problem	Language	Result	Execution time	Memory
503708		Stickfish	NoM (RMI21_nom)	C++17	52 / 100	1086 ms	29796 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];
ll rfact[MAXN];

//ll choose(ll n, ll k) {
    //if (n < 0 || k < 0 || k > n)
        //return 0;
    //return 
//}

ll dp[MAXN][MAXN];
ll choose[MAXN][MAXN];

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

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