题面
设$F(x)=\sum_{i=0}^\infty f_ix^i, G(x)=\sum_{i=0}^\infty g_ix^i$ 未给出即为0
$\therefore~F(x)*G(x)=F(x)(\because g_0=0)$
$\therefore~F(x)=\frac 1{1-G(x)}$
多项式求逆板子一顿套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
106
107
108
using namespace std;
const int mod = 998244353, G = 3, Ginv = (998244353 + 1) / 3;
int f[520010], g[520010], h[520010];
int rev[520010];
inline void der(int *a, int sizea, int *c) {
for(int i = 0; i < sizea - 1; i++)
c[i] = 1ll * a[i + 1] * (i + 1) % mod;
}
inline int power(int a, int b) {
long long res = a, ans = 1;
for(; b; b >>= 1, res = res * res % mod) if(b & 1) ans = ans * res % mod;
return ans;
}
int inv[520010];
inline void integ(int *a, int sizea, int *c) {
inv[1] = 1;
for(int i = 2; i <= sizea; i++) {
inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
}
c[0] = 0;
for(int i = 1; i <= sizea; i++) {
c[i] = 1ll * a[i - 1] * inv[i] % mod;
}
}
inline void get_rev(int l) {
for(int i = 1; i < (1 << l); i++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
}
inline void ntt(int *a, int l, int type) {
for(int i = 0; i < (1 << l); i++)
if(i < rev[i]) swap(a[i], a[rev[i]]);
for(int p = 1; p < (1 << l); p <<= 1) {
int wn = power(type == 1 ? G : Ginv, (mod - 1) / p / 2);
for(int s = 0; s < (1 << l); s += p << 1) {
int w = 1;
for(int i = 0; i < p; i++) {
int h1 = a[s + i], h2 = 1ll * w * a[s + i + p] % mod;
a[s + i] = (h1 + h2) % mod;
a[s + i + p] = (h1 - h2 + mod) % mod;
w = 1ll * w * wn % mod;
}
}
}
if(type == -1) {
int inv = power(1 << l, mod - 2);
for(int i = 0; i < (1 << l); i++) a[i] = 1ll * a[i] * inv % mod;
}
}
inline void mult(int *a, int sizea, int *b, int sizeb, int *c) {
int l;
for(l = 0; (1 << l) < sizea + sizeb - 1; l++);
get_rev(l);
for(int i = 0; i < (1 << l); i++) {
f[i] = (i < sizea ? a[i] : 0);
g[i] = (i < sizeb ? b[i] : 0);
}
ntt(f, l, 1);
ntt(g, l, 1);
for(int i = 0; i < (1 << l); i++) f[i] = 1ll * f[i] * g[i] % mod;
ntt(f, l, -1);
for(int i = 0; i < sizea + sizeb - 1; i++) c[i] = f[i];
}
inline void funcinv(int *a, int sizea, int *b, int sizeb) {
b[0] = power(a[0], mod - 2);
for(int now = 1; now < sizeb; now <<= 1) {
mult(b, now, b, now, h);
mult(h, now + now - 1, a, min(sizea, now << 1), h);
for(int i = 0; i < now << 1; i++) {
if(i < now) b[i] = (2ll * b[i] - h[i] + mod) % mod;
else b[i] = (mod - h[i]) % mod;
}
}
}
int ap[520010];
inline void ln(int *a, int sizea, int *b, int sizeb) {
funcinv(a, sizea, b, sizeb - 1);
der(a, min(sizea, sizeb), ap);
mult(ap, min(sizea, sizeb) - 1, b, sizeb - 1, ap);
integ(ap, sizeb - 1, b);
b[0] = 0;
}
int tmp[520010];
inline void exp(int *a, int sizea, int *b, int sizeb) {
b[0] = 1;
for(int now = 1; now < sizeb; now <<= 1) {
/*f= f0 + (a - ln f0) * f0*/
ln(b, now, tmp, now << 1);
for(int i = 0; i < now << 1; i++) {
if(i < sizea) tmp[i] = (a[i] - tmp[i] + mod) % mod;
else tmp[i] = (mod - tmp[i]) % mod;
}
mult(tmp, now << 1, b, now, tmp);
for(int i = 0; i < now << 1; i++) {
if(i < now) b[i] = (b[i] + tmp[i]) % mod;
else b[i] = tmp[i];
}
}
}
int a[520010], b[520010], n;
int main() {
scanf("%d", &n);
for(int i = 1; i < n; i++) scanf("%d", a + i), a[i] = (mod - a[i]) % mod;
a[0] = 1;
funcinv(a, n, b, n);
for(int i = 0; i < n; i++) printf("%d ", b[i]);
return 0;
}
PS:当然分治FFT也是要学的
类似cdq分治，先递归左边，算出左边对右边的影响(FFT/NTT)，然后递归右边