分治NTT——P4721

分治NTT，套了个dls自动取模的整数板子，但常数过大。

#include <assert.h>
#include <cstdio>
#include <iostream>
using namespace std;
using ll = long long;

const int NR = 1 << 21;
const int G = 3, Gi = 332748118;
const int mod = 998244353;

template <int MOD, int RT>
struct mint
{
    static const int mod = MOD;
    static constexpr mint rt() { return RT; } // primitive root for FFT
    int v;
    explicit operator int() const { return v; } // explicit -> don't silently convert to int
    mint() : v(0) {}
    mint(ll _v)
    {
        v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
        if (v < 0)
            v += MOD;
    }
    bool operator==(const mint &o) const
    {
        return v == o.v;
    }
    friend bool operator!=(const mint &a, const mint &b)
    {
        return !(a == b);
    }
    friend bool operator<(const mint &a, const mint &b)
    {
        return a.v < b.v;
    }

    mint &operator+=(const mint &o)
    {
        if ((v += o.v) >= MOD)
            v -= MOD;
        return *this;
    }
    mint &operator-=(const mint &o)
    {
        if ((v -= o.v) < 0)
            v += MOD;
        return *this;
    }
    mint &operator*=(const mint &o)
    {
        v = int((ll)v * o.v % MOD);
        return *this;
    }
    mint &operator/=(const mint &o) { return (*this) *= inv(o); }
    friend mint pow(mint a, ll p)
    {
        mint ans = 1;
        assert(p >= 0);
        for (; p; p /= 2, a *= a)
            if (p & 1)
                ans *= a;
        return ans;
    }
    friend mint inv(const mint &a)
    {
        assert(a.v != 0);
        return pow(a, MOD - 2);
    }

    mint operator-() const { return mint(-v); }
    mint &operator++() { return *this += 1; }
    mint &operator--() { return *this -= 1; }
    friend mint operator+(mint a, const mint &b) { return a += b; }
    friend mint operator-(mint a, const mint &b) { return a -= b; }
    friend mint operator*(mint a, const mint &b) { return a *= b; }
    friend mint operator/(mint a, const mint &b) { return a /= b; }
};

using mi = mint<mod, 3>;

int rev[NR];

void NTT(mi *a, int n, int type)
{
    for (int i = 0; i < n; ++i)
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int k = 1; k < n; k <<= 1)
    {
        mi wn = pow((type == 1 ? mi(G) : mi(Gi)), (mod - 1) / (k << 1));
        for (int i = 0; i < n; i += (k << 1))
        {
            mi w = mi(1);
            for (int j = 0; j < k; ++j, w = w * wn)
            {
                mi x = a[i + j], y = w * a[i + j + k];
                a[i + j] = x + y;
                a[i + j + k] = x - y;
            }
        }
    }
    if (type == 1)
        return;
    mi invn = inv(mi(n));
    for (int i = 0; i < n; ++i)
        a[i] = a[i] * invn;
}

int n;
mi A[NR], B[NR], C[NR],D[NR];

void cdq(int l, int r)
{
    if(l==r)return ;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    int bit = 0, num = 1;
    while(num<((r-l+1)<<1))
        num <<= 1, bit += 1;
    for (int i = 0; i < num; ++i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    for (int i = 0; i < num;++i)
        C[i] = D[i] = 0;
    for (int i = l; i <= r;++i)
        C[i - l] = A[i - l];
    for (int i = l; i <= mid;++i)
        D[i - l] = B[i];
    NTT(C, num, 1), NTT(D, num, 1);
    for (int i = 0; i < num;++i)
        C[i] = C[i] * D[i];
    NTT(C, num, 0);
    for (int i = mid + 1; i <= r;++i)
        B[i] += C[i - l];
    cdq(mid + 1, r);
}


int main()
{
    scanf("%d", &n);
    for (int i = 1,x; i <= n-1;++i){
        scanf("%d", &x);
        A[i] = mi(x);
    }
    B[0] = mi(1);
    cdq(0, n-1);
    for (int i = 0; i <= n - 1;++i)
        printf("%d ", B[i].v);
}