Submission #44768767

---

Source Code Expand

#include <bits/stdc++.h>

#include <atcoder/all>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T>
bool chmax(T& a, const T& b) {
    return a < b ? (a = b, 1) : 0;
}
template <typename T>
bool chmin(T& a, const T& b) {
    return a > b ? (a = b, 1) : 0;
}

using mint = atcoder::modint998244353;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0; i < (int)v.size(); ++i) {
        os << v[i];
        if (i < (int)v.size() - 1) os << " ";
    }
    return os;
}
ostream& operator<<(ostream& os, const mint& n) {
    os << n.val();
    return os;
}

template <typename mint>
class RelaxedConvolution {
   public:
    mint get(mint a, mint b) {
        f.push_back(a);
        g.push_back(b);
        ++n;
        int m = 1 << __builtin_ctz(n + 1);
        int s = 0, x = 1;
        while (x <= m) {
            calc(n - x, n, s, s + x);
            if (n + 1 == m && x == m >> 1) break;
            calc(s, s + x, n - x, n);
            s += x;
            x <<= 1;
        }
        return h[n - 1];
    }

   private:
    int n = 0;
    std::vector<mint> f, g, h;

    void calc(int lf, int rf, int lg, int rg) {
        if ((int)h.size() < rf + rg - 1) {
            h.resize(rf + rg - 1);
        }
        auto res = atcoder::convolution(
            std::vector<mint>(f.begin() + lf, f.begin() + rf),
            std::vector<mint>(g.begin() + lg, g.begin() + rg));
        for (int i = 0; i < (int)res.size(); ++i) {
            h[lf + lg + i] += res[i];
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int N;
    cin >> N;
    vector<int> A(N + 1);
    rep(i, 1, N + 1) cin >> A[i];

    vector<mint> F(N + 1);
    vector<mint> G(N + 2);

    RelaxedConvolution<mint> conv;
    conv.get(1, 1);
    F[0] = G[1] = 1;

    rep(i, 1, N + 1) {
        F[i] = A[i] * G[i];
        G[i + 1] = G[i] + conv.get(F[i], F[i]);
    }

    rep(i, 1, N + 1) cout << F[i].val() << (i < N ? " " : "\n");
}

Submission Info

Judge Result