§ 1 例题一
=> luogu 4721 【模板】分治 FFT
§ 1.1 题意
给定长度为 $n-1$ 的数组 $g[1],\ g[2],\cdots,g[n-1]$,求 $f[0],\ f[1],\cdots,\ f[n-1]$,其中
边界为 $f[0]=1$。答案对 $998244353$ 取模。
$2\leq n\leq 10^5,\ \ 0\leq g[i]\lt 998244353$。
§ 1.2 分析
令 $P_{\ l,r}$ 表示多项式 $P$ 的第 $l\sim r$ 项系数,即 $P[l],\ P[l+1],\cdots,P[r]$。
观察发现,题目要求的数组 $f$ 类似于卷积,但后面的项与前面有关,不能直接 ${\rm FFT}$。
考虑分治求解,假设已知 $f_{\,l,mid}$,我们需要求出其对 $f_{\,mid+1,r}$ 的贡献。改写定义可得
可以发现左半部分对右半部分贡献为
上式左边可看作 $f_{\,l,mid} \bigotimes g_{\,0,r-l}$(其中 $\bigotimes$ 为卷积符号)。
由于模数为 $998244353$,直接用原根 $G=3$ 的 ${\rm NTT}$ 求解即可。
总时间复杂度为 $O(n\log^2n)$。
§ 1.3 代码
1 | // Let f[i] = sigma{j = 1 .. i} f[i - j] g[j] |
§ 2 例题二
=> [EZOI][1217NOI模拟赛]math(生成函数+分治FFT+高精度) 的子问题
§ 2.1 子问题
求多项式 $\prod\limits_{i=1}^n(x+i)$ 展开后各项的值。
$n\leq 10^5$。
§ 2.2 求解
分治求解,时间复杂度 $T(n)=2\ T(\frac{n}{2})+O(n\log n)=O(n\log^2n)$。
多项式用 vector 存储处理较方便。代码可参考上方链接博文。