Submission #1286700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286700		kami_sama	NoM (RMI21_nom)	C++20	34 / 100	1095 ms	9540 KiB

Main

#include <bits/stdc++.h>

const int maxn = 1e3 + 5;
const int MOD = 1e9 + 7;

#define int long long

int bpow(int a, int p) {
    int r = 1;
    while (p) {
        if (p & 1) {
            r = (1LL * r * a) % MOD;
        }
        a = (1LL * a * a) % MOD;
        p /= 2;
    }

    return r;
}

int inv(int a) { return bpow(a, MOD - 2); }

int fac[maxn];
int ifac[maxn];

int C(int n, int m) {
    int ret = fac[n];

    ret = (1LL * ret * ifac[n - m]) % MOD;
    ret = (1LL * ret * ifac[m]) % MOD;

    return ret;
}

int brute(int n, int m) {
    int ans = 0;
    std::vector<int> perm(2 * n);
    std::iota(perm.begin(), perm.end(), 0);
    do {
        int idx[2 * n] = {};
        for (int i = 0; i < 2 * n; i++) {
            idx[perm[i]] = i;
        }

        bool can = true;
        for (int i = 0; i < n; i++) {
            int j = i + n;
            int d = abs(idx[i] - idx[j]);
            if (d % m == 0) can = false;
        }

        if (can) ans++;
    } while (std::next_permutation(perm.begin(), perm.end()));
    
    return ans;
}

int32_t main() {

    // for (int a = 1; a <= 10; a++) {
    //     for (int b = 1; b <= 2 * a + 1; b++) {
    //         std::cout << a << " " << b << " " << brute(a, b) << '\n';
    //     }
    // }
    // std::cout << "finished\n";

    int n, m;
    std::cin >> n >> m;

    if (m == 1) {
        std::cout << 0;
        return 0;
    }

    fac[0] = 1;
    for (int i = 1; i < maxn; i++) {
        fac[i] = (1LL * i * fac[i - 1]) % MOD;
    }
    ifac[maxn - 1] = inv(fac[maxn - 1]);
    for (int i = maxn - 2; i >= 0; i--) {
        ifac[i] = (1LL * (i + 1) * ifac[i + 1]) % MOD;
    }

    int cnt[m] = {};
    for (int i = 0; i < 2 * n; i++) {
        cnt[i % m]++;
    }

    // int dp[n + 1][n + 1] = {};
    // dp[n][0] = 1;

    std::vector<std::vector<int>> dummy(n + 1, std::vector<int>(n + 1));
    std::vector<std::vector<int>> dp[2];
    dp[0] = dummy;
    dp[0][n][0] = 1;
    for (int i = 0; i < m; i++) {
        dp[1] = dummy;
        for (int a = n; a >= 0; a--) {
            for (int b = n - a; b >= 0; b--) {
                for (int c = std::max(0ll, cnt[i] - b); c <= std::min(a, cnt[i]); c++) {
                    int d = cnt[i] - c;

                    int comb = (C(a, c)) % MOD;
                    comb = (1LL * comb * C(b, d)) % MOD;
                    dp[1][a - c][b - d + c] += (1LL * dp[0][a][b] * comb) % MOD;
                    dp[1][a - c][b - d + c] %= MOD;
                }
            }
        }

        // for (int a = 0; a <= n; a++) {
        //     for (int b = 0; b <= n; b++) {
        //         std::cout << dp[1][a][b] << " ";
        //     }
        //     std::cout << '\n';
        // }
        // std::cout << '\n';
        // std::cout << '\n';

        std::swap(dp[0], dp[1]);
    }

    int ans = dp[0][0][0];
    ans = (bpow(2, n) * ans) % MOD;
    for (int i = 0; i < m; i++) {
        ans = (1LL * ans * fac[cnt[i]]) % MOD;
    }
    

    std::cout << ans;
}

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