Submission #541444

#	Time	Username	Problem	Language	Result	Execution time	Memory
541444		eecs	NoM (RMI21_nom)	C++17	100 / 100	107 ms	428 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int maxn = 4010, P = 1000000007;
int n, m, ans, fact[maxn], finv[maxn], f[2][maxn];

int qp(int x, int y) {
    int z = 1;
    for (; y; y >>= 1, x = 1LL * x * x % P) {
        if (y & 1) z = 1LL * z * x % P;
    }
    return z;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = fact[0] = finv[0] = 1; i < maxn; i++) {
        fact[i] = 1LL * i * fact[i - 1] % P;
        finv[i] = qp(fact[i], P - 2);
    }
    auto binom = [&](int x, int y) {
        return x < y || y < 0 ? 0 : 1LL * fact[x] * finv[y] % P * finv[x - y] % P;
    };
    int cur = 0, nxt = 1;
    f[0][0] = 1;
    for (int i = 0; i < m; i++, swap(cur, nxt)) {
        int l = (2 * n - i - 1) / m + 1;
        memset(f[nxt], 0, sizeof(f[nxt]));
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= min(j, l / 2); k++) {
                f[nxt][j] = (f[nxt][j] + 1LL * f[cur][j - k] * binom(j, k) % P * fact[l] % P * finv[l - 2 * k]) % P;
            }
        }
    }
    for (int i = 0; i <= n; i++) {
        ans = (ans + 1LL * f[cur][i] * binom(n, i) % P * fact[2 * n - 2 * i] % P * (i & 1 ? P - 1 : 1)) % P;
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~

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