前置知识：
FFT
NTT
多项式求逆

分治FFT

分治FFT主要是求解以下问题：

给定序列$g_1\cdots g_{n-1}$，求序列$f_0\cdots f_{n-1}。$
其中$f_i={\sum }_{j=1}^i{f}_{i-j}{g}_j$，边界为$f_0=1$（边界不一定为1，看题目要求）。

模板题在此。
我们主要有两种求解方法，一种是用生成函数构造然后用多项式求逆的方法求解，另一种是CDQ分治法。

第一种解法（多项式求逆）

我们先设$g_0=0$，然后构造生成函数得：$$F(x)=\sum _{i=0}^{\infty }{f}_i{x}^i$$$$G(x)=\sum _{i=0}^{\infty }{g}_i{x}^i$$相乘得：$$F(x)\times G(x)=\sum _{i=0}^{\infty }\sum _{j=0}^{\infty }{f}_i\times g_j\times x^{i+j}$$令$k=i+j$，可得：$$F(x)\times G(x)=\sum _{k=0}^{\infty }(\sum _{j=0}^k{f}_{k-j}\times g_j)x^k$$由于最高次项为$x^{n-1}$，我们可以在模$x^n$的意义下运算，即$$F(x)\times G(x)=\sum _{k=0}^{n-1}(\sum _{j=0}^k{f}_{k-j}\times g_j)x^k$$
$k>0$时${\sum }_{j=0}^k{f}_{k-j}\times g_j=f_k$；
$k=0$时${\sum }_{j=0}^k{f}_{k-j}\times g_j=0$。
所以$F(x)\times G(x)={\sum }_{k=1}^{n-1}{f}_k{x}^k$，刚好和$F(x)$差了一个$f_0$，即$F(x)\times G(x)+f_0=F(x)$。
不难得出：$$F(x)=\frac{f_0}{1-G(x)}$$这样整个过程就完成了，时间复杂度$\Theta (n{\log }^{2}n)$。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define ll long long
using namespace std;
const int N = 1 << 22;
const int g = 3 , gi = 332748118 , mod = 998244353;
ll qw( ll a , ll b ) {
	ll ans = 1;
	while ( b ) {
		if( b & 1 ) {
			ans = ans * a % mod;
		}
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
int rev[N];
int n;
void pre( int bit ) {
	for ( int i = 0 ; i < ( 1 << bit ) ; ++i ) {
		rev[i] = (rev[i>>1]>>1)|((i&1)<<(bit - 1));
	}
}
void NTT( ll *F , int len , int on ) {
	for ( int i = 0 ; i < len ; ++i ) {
		if ( i < rev[i] ) {
			swap( F[i] , F[rev[i]] );
		}
	}
	for ( int i = 2 ; i <= len ; i <<= 1 ) {
		ll gn = qw( on ? g : gi , ( mod - 1 ) / ( i ) );
		for ( int j = 0 ; j <= len - 1 ; j += i ) {
			ll gg = 1;
			for ( int k = j ; k < j + i / 2 ; ++k ) {
				ll u = F[k];
				ll v = gg * F[k + i / 2] % mod;
				F[k] = (u + v) % mod;
				F[k + i / 2] = ( u - v  + mod ) % mod;
				gg = gg * gn % mod;
			}
		}
	}
	return;
}
ll ta[N] , tb[N];
void solve( int len , ll *a , ll *b ) {
	if( len == 1 ) {
		b[0] = qw( a[0] , mod - 2 );
		return;
	}
	solve( ( len + 1 ) >> 1 , a , b );
	int l = 1;
	int bit = 0;
	while ( l <= len + n ) {
		l <<= 1;
		++bit;
	}
	pre( bit );
	for ( int i = 0 ; i < l ; ++i ) {
		ta[i] = a[i];
		tb[i] = ( i < ( ( len + 1 ) >> 1 ) ? b[i] : 0 );
	}
	NTT( ta , l , 1 );
	NTT( tb , l , 1 );
	for ( int i = 0 ; i < l ; ++i ) {
		ta[i] = tb[i] * ( ( ( 2 - ta[i] * tb[i] ) % mod + mod ) % mod ) % mod;
	}
	NTT( ta , l , 0 );
	ll inv = qw( l , mod - 2 );
	for ( int i = 0 ; i < len ; ++i ) {
		b[i] = ta[i] * inv % mod;
	}
}
ll a[N] , b[N];
int main(){
    scanf("%d",&n);
    for ( int i = 1 ; i < n ; ++i ) {
    	scanf("%lld",&a[i]);
    	a[i] = -a[i];
	}
	a[0] = 1;
	solve( n , a , b );
	for ( int i = 0 ; i < n ; ++i ) {
		printf("%lld ",b[i] * 1ll);
	}
    return 0;
} 
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

第二种解法（CDQ分治）

对于式子$f_i={\sum }_{j=1}^i{f}_{i-j}{g}_j$，我们已知$f_0$，那么可以进一步求出$f_1$，然后求出$f_2$，$\cdots$，一直到$f_{n-1}$，这样时间复杂度$\Theta (n^2)$。
我们考虑CDQ分治，目前要求解$i\in [l,r]$所有$f_i$的解。
假设我们已经解得了$f_l\cdots f_{mid}$，下一步考虑如何快速解得$f_{mid+1}\cdots f_r$。
我们可以考虑$f_l\cdots f_{mid}$对$f_{mid+1}\cdots f_r$的贡献。
设$T_i={\sum }_{j=l}^{mid}{f}_{i-j}{g}_j$。
我们用$f_l\cdots f_{mid}$和$g_0\cdots g_{r-l}$去卷积，就可以得到$T_i$序列，累加到$f_{mid+1}\cdots f_r$上面。
$$f_{mid+1}=\sum _{j=1}^{mid+1}{f}_{i-j}{g}_j=\sum _{j=1}^{l-1}{f}_{i-j}{g}_j+\sum _{j=l}^{mid}{f}_{i-j}{g}_j$$
前面的和式在前面的分治已经累加了贡献，后半部分就是$T_i$，加上即可。
我们就这样一直分治下去，时间复杂度$\Theta (n{\log }^{2}n)$。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define ll long long
using namespace std;
const int N = 1 << 22;
const int g = 3 , gi = 332748118 , mod = 998244353;
ll qw( ll a , ll b ) {
	ll ans = 1;
	while ( b ) {
		if( b & 1 ) {
			ans = ans * a % mod;
		}
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
int rev[N];
int n;
void pre( int bit ) {
	for ( int i = 0 ; i < ( 1 << bit ) ; ++i ) {
		rev[i] = (rev[i>>1]>>1)|((i&1)<<(bit - 1));
	}
}
void NTT( ll *F , int len , int on ) {
	for ( int i = 0 ; i < len ; ++i ) {
		if ( i < rev[i] ) {
			swap( F[i] , F[rev[i]] );
		}
	}
	for ( int i = 2 ; i <= len ; i <<= 1 ) {
		ll gn = qw( on ? g : gi , ( mod - 1 ) / ( i ) );
		for ( int j = 0 ; j <= len - 1 ; j += i ) {
			ll gg = 1;
			for ( int k = j ; k < j + i / 2 ; ++k ) {
				ll u = F[k];
				ll v = gg * F[k + i / 2] % mod;
				F[k] = (u + v) % mod;
				F[k + i / 2] = ( u - v  + mod ) % mod;
				gg = gg * gn % mod;
			}
		}
	}
	return;
}
ll f[N] , gg[N];
void mul( ll *a , ll *b , int bit ) {
	pre( bit );
	int len = ( 1 << bit );
	NTT( a , len , 1 );
	NTT( b , len , 1 );
	for ( int i = 0 ; i < len ; ++i ) {
		a[i] = a[i] * b[i] % mod;
	}
	NTT( a , len , 0 );
	ll inv = qw( (ll)len , mod - 2 );
	for ( int i = 0 ; i < len ; ++i ) {
		a[i] = a[i] * inv % mod;
	}
}
ll a[N] , b[N];
void solve( int l , int r ) {
	if( l == r ) {
		return;
	}
	int mid = ( l + r ) >> 1;
	solve( l , mid );
	int bit = 0;
	int len = 1;
	while ( len <= ( mid - l ) + ( r - l ) ) {
		len <<= 1;
		++bit;
	}
	for ( int i = 0 ; i < len ; ++i ) {
		a[i] = b[i] = 0;
	}
	for ( int i = l ; i <= mid ; ++i ) {
		a[i - l] = f[i];
	}
	for ( int i = 0 ; i <= r - l ; ++i ) {
		b[i] = gg[i];
	}
	mul( a , b , bit );
	for( int i = mid + 1 ; i <= r ; ++i ) {
		f[i] = ( f[i] + a[i - l] ) % mod;
	}
	solve( mid + 1 , r );
	return;
}
int main(){
    scanf("%d",&n);
    for ( int i = 1 ; i < n ; ++i ) {
    	scanf("%lld",&gg[i]);
	}
	gg[0] = 0;
	f[0] = 1;
	solve( 0 , n - 1 );
	for ( int i = 0 ; i < n ; ++i ) {
		printf("%lld ",f[i]);
	}
    return 0;
} 
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

其实多项式求逆法时间效率上强于CDQ分治法。