#1087754 (C++23) No.3160 Party Game

• 問題: No.3160 Party Game
• ユーザー: SnowBeenDiding
• 提出日時: 2025-05-23 20:11:59
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,413 bytes
• コンパイル時間: 6,153 ms
• コンパイル使用メモリ: 332,960 KB
• 実行使用メモリ: 55,692 KB
• 最終ジャッジ日時: 2025-05-27 22:00:37
• 合計ジャッジ時間: 11,000 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 3
other	TLE * 2 -- * 36

ソースコード

#include <atcoder/all>
#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace atcoder;
using namespace std;

typedef long long ll;
using mint = modint998244353;

template <typename T, class Conv = void> struct FPS_Base {
    vector<T> a;

    FPS_Base() {}
    FPS_Base(const vector<T> &a_) : a(a_) { normalize(); }
    FPS_Base(int n) { a.assign(n, T(0)); }

    void normalize() {
        while (!a.empty() && a.back() == T(0))
            a.pop_back();
    }

    int size() const { return a.size(); }
    T operator[](int i) const { return (i < a.size() ? a[i] : T(0)); }

    FPS_Base operator+(const FPS_Base &rhs) const {
        int n = max(a.size(), rhs.a.size());
        vector<T> res(n, T(0));
        rep(i, 0, n) res[i] = (*this)[i] + rhs[i];
        return FPS_Base(res);
    }

    FPS_Base operator-(const FPS_Base &rhs) const {
        int n = max(a.size(), rhs.a.size());
        vector<T> res(n, T(0));
        rep(i, 0, n) res[i] = (*this)[i] - rhs[i];
        return FPS_Base(res);
    }

    FPS_Base operator*(const FPS_Base &rhs) const {
        vector<T> res;
        if constexpr (is_same<Conv, void>::value) {
            // res = convolution1000000007(a, rhs.a);
        } else {
            res = convolution(a, rhs.a);
        }
        return FPS_Base(res);
    }

    FPS_Base operator*(const T &c) const {
        vector<T> res = a;
        for (auto &x : res)
            x = x * c;
        return FPS_Base(res);
    }

    FPS_Base truncate(int deg) const {
        vector<T> res(min((int)a.size(), deg));
        rep(i, 0, res.size()) res[i] = a[i];
        return FPS_Base(res);
    }

    FPS_Base rev(int deg = -1) const {
        vector<T> res = a;
        reverse(res.begin(), res.end());
        if (deg != -1) {
            if ((int)res.size() < deg)
                res.resize(deg, T(0));
            else
                res = vector<T>(res.begin(), res.begin() + deg);
        }
        return FPS_Base(res);
    }

    pair<FPS_Base, FPS_Base> divmod(const FPS_Base &rhs) const {
        int n = a.size(), m = rhs.a.size();
        if (n < m)
            return {FPS_Base({T(0)}), *this};
        FPS_Base rev_f = this->rev();
        FPS_Base rev_g = rhs.rev();
        FPS_Base q =
            (rev_f.inv(n - m + 1) * rev_g).truncate(n - m + 1).rev(n - m + 1);
        FPS_Base r = (*this) - (rhs * q);
        r.normalize();
        return {q, r};
    }

    FPS_Base operator/(const FPS_Base &rhs) const { return divmod(rhs).first; }

    FPS_Base operator%(const FPS_Base &rhs) const { return divmod(rhs).second; }

    FPS_Base shift(int shift) const {
        if (shift >= 0) {
            if ((int)a.size() <= shift)
                return FPS_Base();
            vector<T> res(a.begin() + shift, a.end());
            return FPS_Base(res);
        } else {
            int s = -shift;
            vector<T> res(s, T(0));
            res.insert(res.end(), a.begin(), a.end());
            return FPS_Base(res);
        }
    }

    T dot(const FPS_Base &rhs) const {
        int n = min(a.size(), rhs.a.size());
        T res(0);
        rep(i, 0, n) res = res + a[i] * rhs.a[i];
        return res;
    }

    FPS_Base derivative() const {
        if (a.empty())
            return FPS_Base();
        vector<T> res(a.size() - 1);
        rep(i, 1, a.size()) { res[i - 1] = a[i] * T(i); }
        return FPS_Base(res);
    }

    FPS_Base integral() const {
        vector<T> res(a.size() + 1, T(0));
        rep(i, 0, a.size()) { res[i + 1] = a[i] / T(i + 1); }
        return FPS_Base(res);
    }

    T eval(const T &x) const {
        T res(0), cur(1);
        for (auto coef : a) {
            res = res + coef * cur;
            cur = cur * x;
        }
        return res;
    }

    FPS_Base inv(int deg) const {
        FPS_Base res({a[0].inv()});
        int cur = 1;
        while (cur < deg) {
            cur <<= 1;
            FPS_Base temp = (this->truncate(cur)) * (res * res);
            res = (res * T(2) - temp).truncate(cur);
        }
        return res.truncate(deg);
    }

    FPS_Base log(int deg) const {
        FPS_Base f = this->truncate(deg);
        FPS_Base f_deriv = f.derivative();
        FPS_Base inv_f = f.inv(deg);
        FPS_Base res = (f_deriv * inv_f).integral().truncate(deg);
        return res;
    }

    FPS_Base exp(int deg) const {
        if (this->a.empty()) {
            vector<T> ret(deg, T(0));
            if (deg > 0)
                ret[0] = T(1);
            return FPS_Base(ret);
        }
        FPS_Base res({T(1)});
        int cur = 1;
        while (cur < deg) {
            cur <<= 1;
            FPS_Base log_res = res.log(cur);
            FPS_Base truncated = this->truncate(cur);
            FPS_Base diff = truncated - log_res;
            if (diff.a.empty())
                diff.a.resize(cur, T(0));
            diff.a[0] = diff.a[0] + T(1);
            res = (res * diff).truncate(cur);
        }
        return res.truncate(deg);
    }

    FPS_Base pow(long long k, int deg = -1) const {
        const int n = this->size();
        if (deg == -1)
            deg = n;
        if (k == 0) {
            FPS_Base ret(deg);
            if (deg > 0)
                ret.a[0] = T(1);
            return ret;
        }
        for (int i = 0; i < n; i++) {
            if ((*this)[i] != T(0)) {
                T rev = T(1) / (*this)[i];
                FPS_Base tmp = ((*this) * rev).shift(i);
                FPS_Base ret = (tmp.log(deg) * T(k)).exp(deg);
                ret = ret * ((*this)[i].pow(k));
                ret = ret.shift(-(i * k));
                ret = ret.truncate(deg);
                if (ret.size() < deg)
                    ret.a.resize(deg, T(0));
                return ret;
            }
            __int128 prod = ((__int128)(i + 1) * k);
            if (prod >= deg)
                return FPS_Base(deg);
        }
        return FPS_Base(deg);
    }
    T &operator[](int i) {
        if (i >= (int)a.size()) {
            a.resize(i + 1, T(0));
        }
        return a[i];
    }
};

// --- NTT フレンドリー版 ---
template <typename T>
struct FormalPowerSeriesNTTFrendly : public FPS_Base<T, int> {
    using Base = FPS_Base<T, int>;
    FormalPowerSeriesNTTFrendly() : Base() {}
    FormalPowerSeriesNTTFrendly(const vector<T> &a) : Base(a) {}
    FormalPowerSeriesNTTFrendly(int n) : Base(n) {}
};

// --- 自作convolution版 ---
template <typename T> struct FormalPowerSeries : public FPS_Base<T, void> {
    using Base = FPS_Base<T, void>;
    FormalPowerSeries() : Base() {}
    FormalPowerSeries(const vector<T> &a) : Base(a) {}
    FormalPowerSeries(int n) : Base(n) {}
};

using fps = FormalPowerSeriesNTTFrendly<modint998244353>;

mint f(int n, int m, int tar) {
    if (tar < 0)
        return 0;
    fps v(tar + 1);
    m = min(m, tar + 1);
    rep(i, 0, m) { v[i] = 1; }
    auto w = v.pow(n, tar + 1);
    mint ret = 0;
    rep(i, 0, tar + 1) { ret += w[i]; }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<mint> a(m);
    mint sm = 0;
    rep(i, 0, m) { a[i] = f(n, m - i, m - i * n); }
    mint ans = 0;
    mint dec = 0;
    for (int i = m - 1; i >= 0; i--) {
        ans += i * (a[i] - dec);
        sm += (a[i] - dec);
        dec = a[i];
    }
    ans /= sm;
    cout << ans.val() << endl;
}