【学习笔记】分治在FFT上的应用

其实就是cdq分治+FFT。

分治FFT解决的问题的一般形式:

给出$g_1,g_2,g_3\cdots g_{n-1},f_0=1$,且

求$f_1,f_2\cdots f_{n-1}$

先展开观察性质

我们发现如果将整个序列分成两半,前一半对后一半的贡献是:

其中$p\in(\rm{mid},r]$,$o$是额外的贡献。

我们发现,其实这是个卷积的形式,毕竟对于普通的卷积定义是:

于是我们就可以通过分治,每次暴力NTT计算前一半对后一半的贡献,类似于cdq分治的操作,复杂度$n\log ^2n$。

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
int n ;
ll ans[N] ;
ll base[N] ;

namespace Poly{
int k, d ;
int rev[N] ;
int g[18][N] ;
int expow(int x, int y){
int ret = 1 ;
while (y){
if (y & 1)
ret = 1ll * ret * x % P ;
x = 1ll * x * x % P ; y >>= 1 ;
}
return ret ;
}
void pre_rt(){
for (int i = 0 ; i < 18 ; ++ i){
int* r = g[i], ut ; r[0] = 1 ;
ut = r[1] = expow(3, 998244352 / (1 << (i + 1))) ;
for (int j = 2 ; j < (1 << i) ; ++ j) r[j] = (ll)r[j - 1] * ut % P ;
}
}
template <typename T>
void NTT(T *f, int L, bool mk){
int l = 0 ;
for (int i = 0 ; i < L ; ++ i)
if (rev[i] < i) swap(f[i], f[rev[i]]) ;
for (int i = 1 ; i < L ; i <<= 1, ++ l){
int *r = g[l], o = i << 1, rt, irt ;
for (int j = 0 ; j < L ; j += o)
for (int k = j ; k < i + j ; ++ k){
rt = f[k], irt = f[k + i] * r[k - j] % P ;
f[k] = addn(rt, irt), f[k + i] = decn(rt, irt) ;
}
}
if (!mk) return ;
reverse(f + 1, f + L) ;
int o = expow(L, P - 2) ;
for (int i = 0 ; i < L ; ++ i) (f[i] *= o) %= P ;
}
void getlen(int x){
d = 1, k = 0 ;
while (d <= x) d <<= 1, ++ k ;
for (int i = 0 ; i < d ; ++ i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1)) ;
}
ll tl[N] ;
ll tr[N] ;
void cdq(int l, int r){
if (l == r) return ;
int len = r - l + 1 ;
int mid = (l + r) >> 1 ;
int len1 = mid - l + 1 ;
cdq(l, mid) ; getlen(len) ;
memcpy(tl, base, sizeof(ll) * len) ;
memcpy(tr, ans + l, sizeof(ll) * len1) ;
memset(tl + len, 0, sizeof(ll) * (d - len + 1)) ;
memset(tr + len1, 0, sizeof(ll) * (d - len1 + 1)) ;
NTT(tl, d, 0) ; NTT(tr, d, 0) ;
for (int i = 0 ; i < d ; ++ i) (tl[i] *= tr[i]) %= P ;
NTT(tl, d, 1) ;
for (int i = mid + 1 ; i <= r ; ++ i) add(ans[i], tl[i - l]) ;
cdq(mid + 1, r) ;
}
}

嗯,得出结论我的分治没学好qaq

但是如果换一个角度观察,设出两个形式幂级数,即令

然后我们把他俩卷起来,且因为F本身就是卷积的形式,即有:

那么先移项,之后两边同时卷一个$\rm{G}-1$ 的逆就可以得到:

于是直接求一个逆就完了,复杂度$n\log n$。

不得不说这也算是一个小技巧了qwq