【学习笔记】分治在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
void cdqNTT(int l, int r){
if (l == r) {if (!l) F[l] = 1 ; return ;} int i ;
int mid = (l + r) >> 1, L = r - l + 1, Len = 1, l1 = 0 ;
cdqNTT(l, mid) ;
while (Len <= L) Len <<= 1, ++ l1 ;
memcpy (P, G, sizeof(LL) * (r - l + 1)) ;
memcpy (Q, F + l, sizeof(LL)*(mid - l + 1)) ;
memset (P + r - l + 1, 0, sizeof (LL) * (Len - r + l)) ;
memset (Q + mid - l + 1, 0, sizeof (LL) * (Len - mid + l)) ;
for (i = 0 ; i < Len ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l1 - 1)) ;
NTT(P, Len, 1), NTT(Q, Len, 1) ; for (i = 0 ; i < Len ; ++ i) P[i] = P[i] * Q[i] % Mod ;
NTT(P, Len, -1) ; for (i = mid + 1 ; i <= r ; ++ i) (F[i] += P[i - l]) %= Mod ; cdqNTT(mid + 1, r) ;
}
int main(){
cin >> N ; int i ;
for (i = 1 ; i < N ; ++ i) scanf("%lld", &G[i]) ;
cdqNTT(0, N - 1) ; for (i = 0 ; i < N ; ++ i) printf("%lld ", F[i]) ; return 0 ;
}

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

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

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

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

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

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