#799268 (C++17) No.1145 Sums of Powers

提出ソース
結果

問題	No.1145 Sums of Powers
ユーザー	rniya
提出日時	2022-09-20 10:38:47
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	348 ms / 2,000 ms
コード長	15,587 bytes
コンパイル時間	4,643 ms
コンパイル使用メモリ	249,168 KB
実行使用メモリ	8,708 KB
最終ジャッジ日時	2024-12-22 03:23:30
合計ジャッジ時間	6,197 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	3 ms 5,248 KB
testcase_03	AC	335 ms 8,660 KB
testcase_04	AC	342 ms 8,708 KB
testcase_05	AC	348 ms 8,660 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#pragma region Macros
typedef long long ll;
typedef __int128_t i128;
typedef unsigned int uint;
typedef unsigned long long ull;
#define ALL(x) (x).begin(), (x).end()

template <typename T> istream& operator>>(istream& is, vector<T>& v) {
    for (T& x : v) is >> x;
    return is;
}
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    for (size_t i = 0; i < v.size(); i++) {
        os << v[i] << (i + 1 == v.size() ? "" : " ");
    }
    return os;
}
template <typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& m) {
    os << '{';
    for (auto itr = m.begin(); itr != m.end();) {
        os << '(' << itr->first << ',' << itr->second << ')';
        if (++itr != m.end()) os << ',';
    }
    os << '}';
    return os;
}
template <typename T, typename U> ostream& operator<<(ostream& os, const unordered_map<T, U>& m) {
    os << '{';
    for (auto itr = m.begin(); itr != m.end();) {
        os << '(' << itr->first << ',' << itr->second << ')';
        if (++itr != m.end()) os << ',';
    }
    os << '}';
    return os;
}
template <typename T> ostream& operator<<(ostream& os, const set<T>& s) {
    os << '{';
    for (auto itr = s.begin(); itr != s.end();) {
        os << *itr;
        if (++itr != s.end()) os << ',';
    }
    os << '}';
    return os;
}
template <typename T> ostream& operator<<(ostream& os, const multiset<T>& s) {
    os << '{';
    for (auto itr = s.begin(); itr != s.end();) {
        os << *itr;
        if (++itr != s.end()) os << ',';
    }
    os << '}';
    return os;
}
template <typename T> ostream& operator<<(ostream& os, const unordered_set<T>& s) {
    os << '{';
    for (auto itr = s.begin(); itr != s.end();) {
        os << *itr;
        if (++itr != s.end()) os << ',';
    }
    os << '}';
    return os;
}
template <typename T> ostream& operator<<(ostream& os, const deque<T>& v) {
    for (size_t i = 0; i < v.size(); i++) {
        os << v[i] << (i + 1 == v.size() ? "" : " ");
    }
    return os;
}
template <typename T, size_t N> ostream& operator<<(ostream& os, const array<T, N>& v) {
    for (size_t i = 0; i < N; i++) {
        os << v[i] << (i + 1 == N ? "" : " ");
    }
    return os;
}

template <int i, typename T> void print_tuple(ostream&, const T&) {}
template <int i, typename T, typename H, class... Args> void print_tuple(ostream& os, const T& t) {
    if (i) os << ',';
    os << get<i>(t);
    print_tuple<i + 1, T, Args...>(os, t);
}
template <typename... Args> ostream& operator<<(ostream& os, const tuple<Args...>& t) {
    os << '{';
    print_tuple<0, tuple<Args...>, Args...>(os, t);
    return os << '}';
}

void debug_out() { cerr << '\n'; }
template <class Head, class... Tail> void debug_out(Head&& head, Tail&&... tail) {
    cerr << head;
    if (sizeof...(Tail) > 0) cerr << ", ";
    debug_out(move(tail)...);
}
#ifdef LOCAL
#define debug(...)                                                                   \
    cerr << " ";                                                                     \
    cerr << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << '\n'; \
    cerr << " ";                                                                     \
    debug_out(__VA_ARGS__)
#else
#define debug(...) void(0)
#endif

template <typename T> T gcd(T x, T y) { return y != 0 ? gcd(y, x % y) : x; }
template <typename T> T lcm(T x, T y) { return x / gcd(x, y) * y; }

int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(long long t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
int botbit(signed a) { return a == 0 ? 32 : __builtin_ctz(a); }
int botbit(long long a) { return a == 0 ? 64 : __builtin_ctzll(a); }
int popcount(signed t) { return __builtin_popcount(t); }
int popcount(long long t) { return __builtin_popcountll(t); }
bool ispow2(int i) { return i && (i & -i) == i; }
long long MSK(int n) { return (1LL << n) - 1; }

template <class T> T ceil(T x, T y) {
    assert(y >= 1);
    return (x > 0 ? (x + y - 1) / y : x / y);
}
template <class T> T floor(T x, T y) {
    assert(y >= 1);
    return (x > 0 ? x / y : (x - y + 1) / y);
}

template <class T1, class T2> inline bool chmin(T1& a, T2 b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T1, class T2> inline bool chmax(T1& a, T2 b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T> void mkuni(vector<T>& v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}
template <typename T> int lwb(const vector<T>& v, const T& x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); }
#pragma endregion

#include <iostream>
#include "atcoder/modint"

namespace atcoder {

template <int MOD> std::istream& operator>>(std::istream& is, static_modint<MOD>& x) {
    int64_t v;
    x = static_modint<MOD>{(is >> v, v)};
    return is;
}

template <int MOD> std::ostream& operator<<(std::ostream& os, const static_modint<MOD>& x) { return os << x.val(); }

template <int ID> std::ostream& operator<<(std::ostream& os, const dynamic_modint<ID>& x) { return os << x.val(); }

}  // namespace atcoder

#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>

#include "atcoder/convolution"

template <typename T> struct FormalPowerSeries : std::vector<T> {
private:
    using std::vector<T>::vector;
    using FPS = FormalPowerSeries;
    void shrink() {
        while (this->size() and this->back() == T(0)) this->pop_back();
    }

    FPS pre(size_t sz) const { return FPS(this->begin(), this->begin() + std::min(this->size(), sz)); }

    FPS operator>>(size_t sz) const {
        if (this->size() <= sz) return {};
        return FPS(this->begin() + sz, this->end());
    }

    FPS operator<<(size_t sz) const {
        if (this->empty()) return {};
        FPS ret(*this);
        ret.insert(ret.begin(), sz, T(0));
        return ret;
    }

public:
    FPS& operator+=(const FPS& r) {
        if (r.size() > this->size()) this->resize(r.size());
        for (size_t i = 0; i < r.size(); i++) (*this)[i] += r[i];
        shrink();
        return *this;
    }

    FPS& operator+=(const T& v) {
        if (this->empty()) this->resize(1);
        (*this)[0] += v;
        shrink();
        return *this;
    }

    FPS& operator-=(const FPS& r) {
        if (r.size() > this->size()) this->resize(r.size());
        for (size_t i = 0; i < r.size(); i++) (*this)[i] -= r[i];
        shrink();
        return *this;
    }

    FPS& operator-=(const T& v) {
        if (this->empty()) this->resize(1);
        (*this)[0] -= v;
        shrink();
        return *this;
    }

    FPS& operator*=(const FPS& r) {
        auto res = atcoder::convolution(*this, r);
        return *this = {res.begin(), res.end()};
    }

    FPS& operator*=(const T& v) {
        for (auto& x : (*this)) x *= v;
        shrink();
        return *this;
    }

    FPS operator+(const FPS& r) const { return FPS(*this) += r; }

    FPS operator+(const T& v) const { return FPS(*this) += v; }

    FPS operator-(const FPS& r) const { return FPS(*this) -= r; }

    FPS operator-(const T& v) const { return FPS(*this) -= v; }

    FPS operator*(const FPS& r) const { return FPS(*this) *= r; }

    FPS operator*(const T& v) const { return FPS(*this) *= v; }

    FPS operator-() const {
        FPS ret = *this;
        for (auto& v : ret) v = -v;
        return ret;
    }

    FPS differential() const {
        const int n = (int)this->size();
        FPS ret(std::max(0, n - 1));
        for (int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i);
        return ret;
    }

    FPS integral() const {
        const int n = (int)this->size();
        FPS ret(n + 1);
        ret[0] = T(0);
        if (n > 0) ret[1] = T(1);
        auto mod = T::mod();
        for (int i = 2; i <= n; i++) ret[i] = -ret[mod % i] * (mod / i);
        for (int i = 0; i < n; i++) ret[i + 1] *= (*this)[i];
        return ret;
    }

    FPS inv(int deg = -1) const {
        assert((*this)[0] != T(0));
        const int n = (int)this->size();
        if (deg == -1) deg = n;
        FPS ret{(*this)[0].inv()};
        ret.reserve(deg);
        for (int d = 1; d < deg; d <<= 1) {
            FPS f(d << 1), g(d << 1);
            std::copy(this->begin(), this->begin() + std::min(n, d << 1), f.begin());
            std::copy(ret.begin(), ret.end(), g.begin());
            atcoder::internal::butterfly(f);
            atcoder::internal::butterfly(g);
            for (int i = 0; i < (d << 1); i++) f[i] *= g[i];
            atcoder::internal::butterfly_inv(f);
            std::fill(f.begin(), f.begin() + d, T(0));
            atcoder::internal::butterfly(f);
            for (int i = 0; i < (d << 1); i++) f[i] *= g[i];
            atcoder::internal::butterfly_inv(f);
            T iz = T(d << 1).inv();
            iz *= -iz;
            for (int i = d; i < std::min(d << 1, deg); i++) ret.push_back(f[i] * iz);
        }
        return ret.pre(deg);
    }

    FPS log(int deg = -1) const {
        assert((*this)[0] == T(1));
        if (deg == -1) deg = (int)this->size();
        return (differential() * inv(deg)).pre(deg - 1).integral();
    }

    FPS sqrt(const std::function<T(T)>& get_sqrt, int deg = -1) const {
        const int n = this->size();
        if (deg == -1) deg = n;
        if (this->empty()) return FPS(deg, 0);
        if ((*this)[0] == T(0)) {
            for (int i = 1; i < n; i++) {
                if ((*this)[i] != T(0)) {
                    if (i & 1) return {};
                    if (deg - i / 2 <= 0) break;
                    auto ret = (*this >> i).sqrt(get_sqrt, deg - i / 2);
                    if (ret.empty()) return {};
                    ret = ret << (i / 2);
                    if ((int)ret.size() < deg) ret.resize(deg, T(0));
                    return ret;
                }
            }
            return FPS(deg, T(0));
        }
        auto sqrtf0 = T(get_sqrt((*this)[0]));
        if (sqrtf0 * sqrtf0 != (*this)[0]) return {};
        FPS ret{sqrtf0};
        T inv2 = T(2).inv();
        for (int i = 1; i < deg; i <<= 1) ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2;
        return ret.pre(deg);
    }

    /**
     * @brief Exp of Formal Power Series
     *
     * @see https://arxiv.org/pdf/1301.5804.pdf
     */
    FPS exp(int deg = -1) const {
        assert(this->empty() or (*this)[0] == T(0));
        if (this->size() == 0) return {};
        if (this->size() == 1) return {T(1)};
        if (deg == -1) deg = (int)this->size();
        FPS inv;
        inv.reserve(deg + 1);
        inv.push_back(T(0));
        inv.push_back(T(1));
        auto inplace_integral = [&](FPS& F) -> void {
            const int n = (int)F.size();
            auto mod = T::mod();
            while ((int)inv.size() <= n) {
                int i = inv.size();
                inv.push_back(-inv[mod % i] * (mod / i));
            }
            F.insert(F.begin(), T(0));
            for (int i = 1; i <= n; i++) F[i] *= inv[i];
        };
        auto inplace_differential = [](FPS& F) -> void {
            if (F.empty()) return;
            F.erase(F.begin());
            for (size_t i = 0; i < F.size(); i++) F[i] *= T(i + 1);
        };
        FPS f{1, (*this)[1]}, g{T(1)}, g_fft{T(1), T(1)};
        for (int m = 2; m < deg; m <<= 1) {
            const T iz1 = T(m).inv(), iz2 = T(m << 1).inv();
            auto f_fft = f;
            f_fft.resize(m << 1);
            atcoder::internal::butterfly(f_fft);
            {
                // Step 2.a'
                FPS _g(m);
                for (int i = 0; i < m; i++) _g[i] = f_fft[i] * g_fft[i];
                atcoder::internal::butterfly_inv(_g);
                std::fill(_g.begin(), _g.begin() + (m >> 1), T(0));
                atcoder::internal::butterfly(_g);
                for (int i = 0; i < m; i++) _g[i] *= -g_fft[i] * iz1 * iz1;
                atcoder::internal::butterfly_inv(_g);
                g.insert(g.end(), _g.begin() + (m >> 1), _g.end());

                g_fft = g;
                g_fft.resize(m << 1);
                atcoder::internal::butterfly(g_fft);
            }
            FPS x(this->begin(), this->begin() + std::min((int)this->size(), m));
            {
                // Step 2.b'
                x.resize(m);
                inplace_differential(x);
                x.push_back(T(0));
                atcoder::internal::butterfly(x);
            }
            {
                // Step 2.c'
                for (int i = 0; i < m; i++) x[i] *= f_fft[i] * iz1;
                atcoder::internal::butterfly_inv(x);
            }
            {
                // Step 2.d' and 2.e'
                x -= f.differential();
                x.resize(m << 1);
                for (int i = 0; i < m - 1; i++) x[m + i] = x[i], x[i] = T(0);
                atcoder::internal::butterfly(x);
                for (int i = 0; i < (m << 1); i++) x[i] *= g_fft[i] * iz2;
                atcoder::internal::butterfly_inv(x);
            }
            {
                // Step 2.f'
                x.pop_back();
                inplace_integral(x);
                for (int i = m; i < std::min((int)this->size(), m << 1); i++) x[i] += (*this)[i];
                std::fill(x.begin(), x.begin() + m, T(0));
            }
            {
                // Step 2.g' and 2.h'
                atcoder::internal::butterfly(x);
                for (int i = 0; i < (m << 1); i++) x[i] *= f_fft[i] * iz2;
                atcoder::internal::butterfly_inv(x);
                f.insert(f.end(), x.begin() + m, x.end());
            }
        }
        return FPS{f.begin(), f.begin() + deg};
    }

    FPS pow(int64_t k, int deg = -1) const {
        const int n = (int)this->size();
        if (deg == -1) deg = n;
        for (int i = 0; i < n; i++) {
            if ((*this)[i] != T(0)) {
                if (i * k > deg) return FPS(deg, T(0));
                T rev = (*this)[i].inv();
                FPS ret = (((*this * rev) >> i).log(deg) * k).exp(deg) * ((*this)[i].pow(k));
                ret = (ret << (i * k)).pre(deg);
                if ((int)ret.size() < deg) ret.resize(deg, T(0));
                return ret;
            }
        }
        return FPS(deg, T(0));
    }

    T eval(T x) const {
        T ret = 0, w = 1;
        for (const auto& v : *this) ret += w * v, w *= x;
        return ret;
    }
};

const int INF = 1e9;
const long long IINF = 1e18;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const char dir[4] = {'D', 'R', 'U', 'L'};
const long long MOD = 1000000007;
// const long long MOD = 998244353;

using mint = atcoder::modint998244353;
using FPS = FormalPowerSeries<mint>;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for (int& x : A) cin >> x;

    auto calc = [&](auto self, int l, int r) -> pair<FPS, FPS> {
        if (r - l == 1) return make_pair(FPS{1}, FPS{1, -A[l]});
        int m = (l + r) >> 1;
        auto L = self(self, l, m), R = self(self, m, r);
        return make_pair(L.first * R.second + R.first * L.second, L.second * R.second);
    };
    auto res = calc(calc, 0, N);
    auto ans = res.first * res.second.inv(M + 1);
    for (int i = 1; i <= M; i++) cout << ans[i] << (i == M ? '\n' : ' ');
    return 0;
}
yukicoder

結果

テストケース

ソースコード
