結果

問題 No.3770 Sum of Pow of Distinct Count
コンテスト
ユーザー marc2825
提出日時 2026-10-13 03:37:22
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 519 ms / 4,000 ms
+ 662µs
コード長 2,745 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,842 ms
コンパイル使用メモリ 256,740 KB
実行使用メモリ 21,432 KB
最終ジャッジ日時 2026-10-16 20:58:42
合計ジャッジ時間 9,308 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/// GPT6-Astra

#include <bits/stdc++.h>
#include <atcoder/convolution>
#include <atcoder/modint>

using namespace std;

using mint = atcoder::modint998244353;
using Poly = vector<mint>;

struct Block {
    Poly p;
    Poly q;
};

// 半開区間 [l, r) に対応する P, Q を構築する。
Block build(int l, int r, const Poly& t) {
    if (r - l == 1) {
        return {
            Poly{t[l]},
            Poly{mint(1), -mint(l)}
        };
    }

    int m = (l + r) / 2;

    Block left = build(l, m, t);
    Block right = build(m, r, t);

    // P = P_left * Q_right + x^(m-l) * P_right
    Poly p = atcoder::convolution(left.p, right.q);

    int shift = m - l;
    for (int i = 0; i < static_cast<int>(right.p.size()); ++i) {
        p[shift + i] += right.p[i];
    }

    // Q = Q_left * Q_right
    Poly q = atcoder::convolution(left.q, right.q);

    return {move(p), move(q)};
}

// f^(-1) mod x^n を求める。f[0] != 0 が必要。
Poly inverse_series(const Poly& f, int n) {
    Poly g{f[0].inv()};

    while (static_cast<int>(g.size()) < n) {
        int len = min(n, 2 * static_cast<int>(g.size()));
        int take = min(len, static_cast<int>(f.size()));

        Poly h(f.begin(), f.begin() + take);
        h = atcoder::convolution(h, g);
        h.resize(len);

        // h = 2 - f * g
        for (mint& value : h) {
            value = -value;
        }
        h[0] += 2;

        // g <- g * (2 - f * g)
        g = atcoder::convolution(g, h);
        g.resize(len);
    }

    return g;
}

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

    long long N, M;
    int K;
    cin >> N >> M >> K;

    int L = static_cast<int>(
        min({N, M, static_cast<long long>(K)})
    );

    Poly fact(L + 1), inv_fact(L + 1);

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

    inv_fact[L] = fact[L].inv();
    for (int i = L; i >= 1; --i) {
        inv_fact[i - 1] = inv_fact[i] * i;
    }

    // a[i] = (-1)^i * (M-i)^N / i!
    // b[i] = 1 / i!
    Poly a(L + 1);
    Poly b = inv_fact;

    for (int i = 0; i <= L; ++i) {
        a[i] = mint(M - i).pow(N) * inv_fact[i];

        if (i & 1) {
            a[i] = -a[i];
        }
    }

    Poly c = atcoder::convolution(a, b);

    // t[j] = (M)_j * j! * c[j]
    Poly t(L + 1);
    mint falling = 1;

    for (int j = 0; j <= L; ++j) {
        if (j > 0) {
            falling *= mint(M - j + 1);
        }

        t[j] = falling * fact[j] * c[j];
    }

    Block all = build(1, L + 1, t);

    Poly inv_q = inverse_series(all.q, K);
    Poly answer = atcoder::convolution(all.p, inv_q);
    answer.resize(K);

    for (int k = 0; k < K; ++k) {
        cout << answer[k].val() << '\n';
    }
}
0