9
7
2016
0

【抄袭】多项式初步

两个多项式$A(x),B(x),$求$C(x)=A(x)*B(x)$

简单的说,我们可以考虑先在$O(nlogn)$时间内把系数表示的$A(x),B(x)$转成点值表达,再用$O(n)$时间计算出$C(x)$的点值表达,最后用$O(nlogn)$时间内把$C(x)$转换为系数表达。

系数表示转点值表示称为$DFT$,点值表示转系数表示称为$IDFT$

前置技能:单位根

满足$x^n=1$的复数$n$有个,分别为$\omega^k_n=e^{i\frac{2k\pi}{n}}$,其中称$\omega^1_n$位主$n$次单位根.

单位根有些很好的性质:

  1. $\omega^i_n=\omega^{i-1}_n*\omega^1_n$(复平面旋转)
  2. $\omega^j_n\omega^k_n=\omega^{j+k}_n=\omega^{j+k\mod n}_n$(群的性质)
  3. $\omega^{dk}_{dn}=\omega^{k}_n$(互质性质)

(为了方便进行$DFT$和$IDFT$,下文中的$n$均是不小于多项式次数界的最小$2$的幂次)

$DFT$:

系数表示转点值表示中点值的选取是有讲究的。

先记$A(x)=\sum_{i=0}^{n-1}a_ix^i.$计算$A(x)$在n次单位根处的取值。

定义新多项式

$$A^{[0]}(x)=a_0+a_2x+a_4x^2+\cdots+a_{n-2}x^{\frac{n}{2}-1}$$

$$A^{[1]}(x)=a_1+a_3x+\cdots+a_{n-1}x^{\frac{n}{2}-1}$$

开心地发现:

$$A(x)=A[0](x^2)+xA[1](x^2)$$
 
亦即
 
$$A(\omega^k_n)=A^{[0]}(\omega^{2k}_n)+\omega^k_nA^{[1]}(\omega^{2k}_n)$$
 
$$A(\omega^{k+\frac{n}{2}}_n)=A^{[0]}(\omega^{2k}_n)-\omega^k_nA^{[1]}(\omega^{2k}_n)$$
 
转化问题:
 
$A(x)$在$\omega^0_n,\cdots,\omega^{n-1}_n$的值
 
变为

$A^{[0]}(x),A^{[1]}(x)$在$A(\omega^0_n)^2,\cdots,(\omega^{n-1}_n)^2$的值.

次数减半,递归硬艹。

$IDFT$:

$IDFT$实质上就是一个矩阵乘法

$$\left(\begin{array}{ccccc}\omega_{n}^{0} & \omega_{n}^{0} & \omega_{n}^{0} & ... & \omega_{n}^{0} \\\omega_{n}^{0} & \omega_{n}^{1} & \omega_{n}^{2} & ... & \omega_{n}^{n} \\\omega_{n}^{0} & \omega_{n}^{2} & \omega_{n}^{4} & ... & \omega_{n}^{2n} \\...            & ...            & ...            & ... & ...            \\\omega_{n}^{0} & \omega_{n}^{n-1} & \omega_{n}^{2n-2} & ... & \omega_{n}^{n^2-n}\end{array}\right)*\left(\begin{array}{c}a_0 \\a_1 \\a_2 \\... \\a_{n-1}\end{array}\right)=\left(\begin{array}{c}b_0 \\b_1 \\b_2 \\... \\b_{n-1} \\\end{array}\right)$$

关键是找到左边矩阵的逆矩阵。可以构造出来:每个元素取共轭复数,再除以$n$。正确性易证。

到此我们已经可以写出一个常数较大的递归FFT了。

蝴蝶变换

观察到我们的分治是将奇偶分类,即对于每一层我取这层对应位数的0放在一起,1放在一起。

那么最后元素$i$所处的位置,就是将$i$的二进制表示翻转的位置。

引入$Cooley-Tukey$算法的图(点击放大):

可以看到,我们每次取对应的两个元素,进行一次“蝴蝶变换”,即完成快速傅里叶变换章节中的对两个元素进行的操作。

快速数论变换($NTT$)

复数计算常数大,误差大,$NTT$可以做到多项式乘法的过程中取模。

当模数十分特殊时可以用数论变换加速,基于一个极强的等价:

$$g^{\frac{P-1}{m}}\equiv \omega_{m} \pmod{P}$$

其中$g$是$P$的原根。

条件是$2^k|P-1$,其中$2^k>n.$

多项式$A(x)$,求多项式$B(x)$,满足$$A(x)*B(x) \equiv 1 \pmod{x^n}$$

这里我们将使用一种倍增的思想来完成。
首先,当$n = 1 $时, $ B[0] = A[0]^{-1} $.
假如我们已经求出了在模 $ x^{\lceil \frac{t}{2} \rceil}$意义下的答案 $ B_0(x)$,要求在 $ x^t $意义下的答案。
那么:

$$\begin{eqnarray}A(x)*B_0(x) & \equiv & 1 \pmod{x^{\lceil \frac{t}{2} \rceil}} \\A(x)*B(x) & \equiv & 1 \pmod{x^{\lceil \frac{t}{2} \rceil}} \end{eqnarray}$$

由于 $A(x)$逆元$B_0(x)$存在,故得:

$$B(x)-B_0(x) \equiv 0 \pmod{x^{\lceil \frac{t}{2} \rceil}}$$

那么我们将等式各部分平方,展开后得:

$$B^2(x)-2*B(x)*B_0(x)+B_0^2(x) \equiv 0 \pmod{ x^t }$$

两边同乘$A(x)$,利用逆元的性质移项便可得:

$$B(x) \equiv B_0(x)*(2-A(x)*B_0(x)) \pmod{ x^t }$$

上式便可在$O(t \log t)$时间内求出了。
由于每次是倍增的,所以总复杂度可得为 $ O(n \log n) $.

Category: HDU | Tags: | Read Count: 260

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com