Submission #1337680

#TimeUsernameProblemLanguageResultExecution timeMemory
1337680adaawfNoM (RMI21_nom)C++20
100 / 100
452 ms23012 KiB
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long int c[2005][2005], f[2005], g[2005], hh = 2000;
long long int power(long long int a, long long int k) {
    long long int res = 1, h = a;
    while (k) {
        if (k & 1) res = res * h % mod;
        h = h * h % mod;
        k >>= 1;
    }
    return res;
}
long long int C(long long int n, long long int k) {
    if (n < 0 || k < 0 || n < k) return 0;
    return f[n] * g[k] % mod * g[n - k] % mod;
}
int main() {
    f[0] = 1;
    for (int i = 1; i <= hh; i++) f[i] = f[i - 1] * i % mod;
    g[hh] = power(f[hh], mod - 2);
    for (int i = hh - 1; i >= 0; i--) g[i] = g[i + 1] * (i + 1) % mod;
    int n, m, d = 0;
    cin >> n >> m;
    n *= 2;
    c[0][0] = 1;
    long long int res = 1;
    for (int i = 0; i < m; i++) {
        int h = n / m;
        if (n % m > i) h++;
        for (int j = 0; j <= n / 2; j++) {
            if (c[i][j] == 0) continue;
            int k = ((n - d) - j) / 2;
            //cout << i << " " << j << " " << c[i][j] << '\n';
            /*int x = j - h, y = j + h;
            if (x < 0) x = h - j;
            if (k < h) y = j - (h - k) + k;
            cout << i << " " << j << " " << x << " " << y << '\n';*/
            for (int l = 0; l <= j; l++) {
                if (h - l > k || l > h) continue;
                long long int d = C(j, l) * C(k, h - l) % mod * f[h] % mod;
                c[i + 1][j - l + h - l] = (c[i + 1][j - l + h - l] + c[i][j] * d) % mod;
            }
        }
        d += h;
    }
    res = res * c[m][0] % mod;
    for (int i = 1; i <= n / 2; i++) res = res * 2 % mod;
    cout << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...