提出 #68064248

---

ソースコード 拡げる

#include <bits/stdc++.h>

using std::cin;
using std::cout;

constexpr int N = 4005;
constexpr int MOD = 924844033;
int n, k, dp[N][N], cnt = 0;
bool marked[N];
long long fact[N], ans = 0;

void Mark(const int val) {
    cnt += val;
    marked[cnt] = false;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> k;

    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    memset(marked, true, sizeof(marked));
    marked[0] = false;
    for (int i = 1; i <= (n - k) % k; i++) {
        Mark(ceil(static_cast<double>(n - k) / k));
        Mark(ceil(static_cast<double>(n - k) / k));
    }

    for (int i = 1; i <= k - (n - k) % k; i++) {
        Mark((n - k) / k);
        Mark((n - k) / k);
    }

    dp[0][0] = 1;
    for (int i = 1; i <= cnt; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = dp[i - 1][j] % MOD;
            if (j > 0) {
                dp[i][j] = (dp[i][j] + dp[i - 1 - marked[i - 1]][j - 1]) % MOD;
            }
        }
    }

    for (int i = 0; i <= n; i++) {
        if (i & 1) {
            ans = ((ans - dp[cnt][i] * fact[n - i] % MOD) % MOD + MOD) % MOD;
        } else {
            ans = (ans + dp[cnt][i] * fact[n - i] % MOD) % MOD;
        }
    }

    cout << ans << "\n";

    return 0;
}

提出情報

ジャッジ結果