結果

問題 No.2763 Macaron Gift Box
ユーザー eve__fuyukieve__fuyuki
提出日時 2024-05-17 23:32:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,742 ms / 3,000 ms
コード長 4,792 bytes
コンパイル時間 4,249 ms
コンパイル使用メモリ 248,848 KB
実行使用メモリ 17,896 KB
最終ジャッジ日時 2024-05-17 23:32:46
合計ジャッジ時間 13,450 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 734 ms
10,124 KB
testcase_08 AC 146 ms
6,940 KB
testcase_09 AC 367 ms
6,944 KB
testcase_10 AC 1,653 ms
17,176 KB
testcase_11 AC 1,641 ms
17,384 KB
testcase_12 AC 1,742 ms
17,768 KB
testcase_13 AC 1,705 ms
17,896 KB
testcase_14 AC 147 ms
6,944 KB
testcase_15 AC 146 ms
6,940 KB
testcase_16 AC 151 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/convolution>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}
class FPS {
    using vec = vector<mint>;

   public:
    vec f;

    // constructor
    FPS() { f = {0}; }
    FPS(int n) { f = vec(n, 0); }
    FPS(vec a) { f = a; }
    FPS(vector<int> &a) {
        f = vector<mint>(a.size());
        for (int i = 0; i < a.size(); i++) {
            f[i] = a[i];
        }
    }
    FPS(const FPS &a) { f = a.f; }

    // useful unary operator
    mint &operator[](int n) { return f[n]; }
    int size() { return (int)f.size(); }
    void resize(int n) { f.resize(n); }

    FPS &operator+=(const FPS &rhs) {
        auto r = rhs.f;
        if (r.size() > f.size()) {
            f.resize(r.size());
        }
        for (int i = 0; i < (int)r.size(); i++) {
            f[i] += r[i];
        }
        return *this;
    }
    FPS &operator+=(const mint &r) {
        if (f.empty()) {
            f.resize(1);
        }
        f[0] += r;
        return *this;
    }
    FPS &operator-=(const FPS &rhs) {
        auto r = rhs.f;
        if (r.size() > f.size()) {
            f.resize(r.size());
        }
        for (int i = 0; i < (int)r.size(); i++) {
            f[i] -= r[i];
        }
        return *this;
    }
    FPS &operator-=(const mint &r) {
        if (f.empty()) {
            f.resize(1);
        }
        f[0] -= r;
        return *this;
    }
    FPS &operator*=(const FPS &rhs) {
        f = convolution(f, rhs.f);
        return *this;
    }
    FPS &operator*=(const mint &r) {
        for (int i = 0; i < f.size(); i++) {
            f[i] *= r;
        }
        return *this;
    }
    FPS &operator/=(const mint &r) {
        assert(r != 0);
        for (int i = 0; i < f.size(); i++) {
            f[i] /= r;
        }
        return *this;
    }
    FPS operator+(const FPS &r) const { return FPS(*this) += r; }
    FPS operator+(const mint &v) const { return FPS(*this) += v; }
    FPS operator-(const FPS &r) const { return FPS(*this) -= r; }
    FPS operator-(const mint &v) const { return FPS(*this) -= v; }
    FPS operator*(const FPS &r) const { return FPS(*this) *= r; }
    FPS operator*(const mint &v) const { return FPS(*this) *= v; }
    FPS operator/(const mint &v) const { return FPS(*this) /= v; }
    FPS operator-() const {
        FPS ret(f.size());
        for (int i = 0; i < f.size(); i++) {
            ret[i] = -f[i];
        }
        return ret;
    }

    FPS inv(int n = -1) const {
        assert(f[0] != 0);
        FPS ret(1);
        ret[0] = f[0].inv();
        if (n == -1) {
            n = f.size();
        }
        int sz = 1;
        while (ret.size() < n) {
            ret = -ret * ((*this) * ret - mint::raw(2));
            sz *= 2;
            ret.resize(sz);
        }
        ret.resize(n);
        return ret;
    }
    FPS &operator/=(FPS &rhs) {
        f = convolution(f, rhs.inv().f);
        return *this;
    }
    FPS operator/(FPS &r) const { return FPS(*this) /= r; }

    FPS diff() const {
        FPS ret(f.size() - 1);
        for (int i = 0; i < f.size() - 1; i++) {
            ret[i] = f[i + 1] * (i + 1);
        }
        return ret;
    }
    FPS integral(mint c = mint::raw(0)) const {
        FPS ret(f.size() + 1);
        ret[0] = c;
        for (int i = 0; i < f.size(); i++) {
            ret[i + 1] = f[i] / (i + 1);
        }
        return ret;
    }
    FPS log(int deg = -1) const {
        assert(f[0] == 1);
        if (deg == -1) {
            deg = f.size();
        }
        auto ret = this->diff() * this->inv(deg);
        ret.resize(deg - 1);
        return ret.integral();
    }
    FPS exp(int deg = -1) const {
        assert(f[0] == 0);
        if (deg == -1) {
            deg = f.size();
        }
        FPS ret(1);
        ret[0] = 1;
        int sz = 1;
        while (ret.size() < deg) {
            sz *= 2;
            ret = ret * ((*this) + mint::raw(1) - ret.log(sz));
            ret.resize(sz);
        }
        ret.resize(deg);
        return ret;
    }
};

int main() {
    fast_io();
    int n, k;
    cin >> n >> k;
    vector<mint> inv(n + 1);
    for (int i = 1; i <= n; i++) {
        inv[i] = mint(i).inv();
    }
    FPS logf(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n / i; j++) {
            logf[i * j] += inv[j];
        }
    }
    FPS f = logf.exp(n + 1);
    FPS finv = f.inv(n + 1);
    // g = finv(x ^ (k + 1))
    FPS g(n + 1);
    for (int i = 0; i <= n / (k + 1); i++) {
        g[i * (k + 1)] = finv[i];
    }
    f *= g;
    for (int i = 1; i <= n; i++) {
        cout << f[i].val() << (i == n ? "\n" : " ");
    }
    return 0;
}
0