9
7
2016
2

【抄袭】多项式初步

两个多项式$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: 1262
www.njmcdirect.com t 说:
2022年8月20日 02:20

The NJMCDirect online portal has eventually replaced the old queuing system. Whenever once violates the traffic or parking rules. www.njmcdirect.com ticket payment online The traffic officers provide a traffic ticket stating your offenses and fine to pay. These compel you to pay the fines within the stated time frame. Violators need to visit the court and queue for long hours. However, the New Jersey Meadowlands Commission

AP SSC computer Ques 说:
2022年9月11日 01:03

Since the Government of AP also provided Computer labs for students in all Government schools also.Computer Knowledge is very much essential nowadays. Even Checking the Results of various examinations, AP SSC computer Question Paper Downloading hall tickets and study materials for multiple exams and booking tickets etc ..need minimum Technical Knowledge is much more important for everyone. Since the Government of AP also provided Computer labs for students in all Government schools also.


登录 *


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