分治 FFT

前置知识：CDQ分治

分治FFT描述的是一类半在线DP方程的卷积优化。

P4721 【模板】分治 FFT
注意

本题也可用多项式求逆解决。

给定序列 \(g_{1\dots n - 1}\)，求序列 \(f_{0\dots n - 1}\)。

其中 \(f_i=\sum_{j=1}^if_{i-j}g_j\)，边界为 \(f_0=1\)。

答案对 \(998244353\) 取模。

\(2\leq n\leq 10^5\)， \(0\leq g_i<998244353\)。

我们应用CDQ分治，先求出 \(f_{[l,mid)}\)，再求对 \(f_{[mid, r)}\) 的贡献。

由题中公式可以发现，多项式 \(f_{[l,mid)} * g_{[0, r-l)}\) 正好就是对 \(f_{[mid, r)}\) 的贡献。

实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const ll p = 998244353, g = 3;
ll qpow(ll a, ll b)
{
    static ll res;
    for (res = 1; b; b >>= 1, a = a * a % p)
        if (b & 1) res = res * a % p;
    return res;
}
ll inv(ll x) { return qpow(x, p - 2); }
const ll gi = inv(g);
const int MAXN = 2e5 + 10;
int n, rev[MAXN], m;
ll F[MAXN], G[MAXN], A[MAXN], B[MAXN];
void NTT(ll *A, int n, int op)
{
    for (int i = 0; i < n; i++)
        if (i < rev[i]) swap(A[i], A[rev[i]]);
    for (int i = 2; i <= n; i <<= 1)
    {
        ll g1 = qpow(op == 1 ? g : gi, (p - 1) / i);
        for (int j = 0; j < n; j += i)
        {
            ll gk = 1;
            for (int k = j; k < j + i / 2; k++)
            {
                ll x = A[k], y = A[k + i / 2] * gk % p;
                A[k] = (x + y) % p;
                A[k + i / 2] = (x - y + p) % p;
                gk = gk * g1 % p;
            }
        }
    }
    if (op == 1) return;
    const ll ni = inv(n);
    for (int i = 0; i < n; i++) A[i] = A[i] * ni % p;
}
void solve(int l, int r) // [l, mid) -> [mid, r)
{
    if (r - l < 2) return;
    int mid = (l + r) >> 1, len;
    solve(l, mid);
    copy(F + l, F + mid, A), copy(G, G + r - l, B);
    for (len = 1; len < r - l; len <<= 1);
    for (int i = 0; i < len; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (len >> 1));
    NTT(A, len, 1), NTT(B, len, 1);
    for (int i = 0; i < len; i++) A[i] = A[i] * B[i] % p;
    NTT(A, len, -1);
    for (int i = mid; i < r; i++) F[i] = (F[i] + A[i - l]) % p;
    fill(A, A + len, 0), fill(B, B + len, 0);
    solve(mid, r);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    F[0] = 1;
    cin >> n;
    for (int i = 1; i < n; i++) cin >> G[i];
    solve(0, n);
    for (int i = 0; i < n; i++) cout << F[i] << " ";
    return 0;
}