oj.uz

Submission #503704

# Submission time Handle Problem Language Result Execution time Memory
503704 2022-01-08T15:52:42 Z Stickfish NoM (RMI21_nom) C++17
0 / 100
 2 ms 332 KB 
#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);
    //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;
            }
            //cout << dp[i][c] << ' ';
        }
        smsz += szi;
        //cout << endl;
    }
    cout << dp[m - 1][n] * pw(2, n) % MOD << endl;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -