分治在FFT上的应用

其实就是cdq分治+FFT。

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

给出$g_1,g_2,g_3\cdots g_{n-1},f_0=1$,且
$$
f_i=\sum_{j=1}^{i} f_{i-j} g_j
$$
求$f_1,f_2\cdots f_{n-1}$

先展开观察性质
$$
\begin{aligned}f_1&=g_1f_0,\\ f_2&=g_1f_1+g_2f_0,
\\ f_3&=g_1f_2+g_2f_1+g_3f_0\\ f_4&=g_1f_3+g_2f_2+g_3f_1+g_4f_0=g_1^4\end{aligned}
$$
我们发现如果将整个序列分成两半,前一半对后一半的贡献是:
$$
o_p=\sum_{i=l}^{\rm{mid}}f_ig_{p-i}
$$
其中$p\in(\rm{mid},r]$,$o$是额外的贡献。

我们发现,其实这是个卷积的形式,毕竟对于普通的卷积定义是:
$$
c_i=\sum_{j\leq i} a_jb_{i-j}
$$
于是我们就可以通过分治,每次暴力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

但是如果换一个角度观察,设出两个形式幂级数,即令
$$
\begin{aligned}
\rm{F}&=\sum f_ix^i\\\
\rm{G}&=\sum g_ix^i
\end{aligned}
$$
然后我们把他俩卷起来,且因为F本身就是卷积的形式,即有:
$$
\begin{aligned}
\rm{F} *\rm{G} & =\sum x^i\sum_{j\leq i} f_ig_j
\\\
&= \sum x_i f_{i+1}\\\
&= \rm{F}-f_0
\end{aligned}
$$
那么先移项,之后两边同时卷一个$\rm{G}-1$ 的逆就可以得到:
$$
\rm{F}= \frac{1}{1-G}
$$
于是直接求一个逆就完了,复杂度$n\log n$。

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