洛谷 P4245 【模板】MTT
题目背景
模板题，无背景
题目描述
给定 $2$ 个多项式 $F(x), G(x)$ ，请求出 $F(x) * G(x)$ 。
系数对 $p$ 取模，且不保证 $p$ 可以分解成$ p = a \cdot 2^k + 1$ 之形式。
输入输出格式
输入格式：
输入共 $3$ 行。
第一行 $3$个整数$ n, m, p$ ，分别表示 $F(x), G(x)$ 的次数以及模数 $p$ 。
第二行为 $n+1$ 个整数， 第 $i$ 个整数 $a_i$ 表示 $F(x)$ 的 $i-1$ 次项的系数。
第三行为 $m+1$个整数， 第 $i$ 个整数 $b_i$ 表示 $G(x)$ 的 $i-1$ 次项的系数。
输出格式：
输出$ n+m+1$ 个整数， 第 $i$ 个整数 $c_i$ 表示$ F(x) * G(x)$ 的 $i-1$次项的系数。
说明
$1 \leq n \leq 10^5, 0 \leq a_i, b_i \leq 10^9, 2 \leq p \leq 10^9 + 9$
拆系数FFT裸题。第一次写拆系数FFT，主要是想记录一下基本知识点。
首先，遇到这种模数不是 $998244353$ 这种好的$a \cdot 2^k+1$形式的质数时显然不能上NTT。为什么不上FFT呢？因为结果很可能非常大，以double和long double 直接存储精度爆炸。因此，拆系数FFT就是通过把原来的结果拆成精度在可接受范围内的几个数，再通过运算得到答案。
具体操作过程如下：
设$F(x)=\sum_{i=0}^{n-1}a_ix^i$，$G(x)=\sum_{i=0}^{n-1}b_ix^i$，考虑求$F(x)*G(x)$各项系数模$p$的值。
首先将$a_i$和$b_i$对$p$取模作为新的$a_i$,$b_i$。
设$M=\lfloor \sqrt p \rfloor$，现在把$a_i$和$b_i$都写成$cM+d$的形式，即对$M$做了一次带余除法。
下面设$a_i=c_iM+d_i$，$b_i=e_iM+f_i$。代入原来的答案式得到第$k$项系数的表达式：
这样处理之后，$c_ie_{k-1},c_if_{k-i},d_ie_{i-k},d_if_{k-i}$在大多数时候都在long long的范围内，而$M$和$M^2$都不会超过$p$，所以如果我们分别对$c_i$和$e_i$、$c_i$和$f_i$、$d_i$和$e_i$、$d_i$和$f_i$做FFT就可以得到答案。
然而这样做的话直接搞需要4次DFT和3次IDFT(其中$c_if_{k-i}$和$d_ie_{i-k}$可以分别做1次DFT，点值相加后再做1次IDFT)。
这里有一种优化常数的方法，来自毛啸的集训队论文:
我们对$a’_i=c_i i +d_i$和$b’_i=e_i i +f_i$（这里$c_i$和$e_i$之后的$i$是虚数单位）做一次卷积，答案的第$k$项就是：
也就是说，第$k$项的虚部就储存了$\sum_{i=0}^k(c_if_{k-i}+d_ie_{i-k})$,实部储存了$\sum_{i=0}^k(d_if_{k-i}-c_ie_{k-i})$,只需要再求出$d_i$和$f_i$的卷积或者$c_i$和$e_i$的卷积就做完了。这样做就需要4次DFT和2次IDFT。
不优秀且丑的代码，似乎不用long double 的话精度过不去。
1 |
|