这是一道模板题。 给你两个多项式,请输出乘起来后的多项式。 输入格式 第一行两个整数 n n 和 m m ,分别表示两个多项式的次数。 第二行 n+1 n+1 个整数,表示第一个多项式的 0 0 到 n n 次项系数。 第三行 m+1 m+1 个整数,表示第二个多项式的 0 0 到 m m 次项系数。 输出格式 一行 n+m+1 n+m+1 个整数,表示乘起来后的多项式的 0 0 到 n+m n+m 次项系数。 样例一 input 1 2 1 2 1 2 1

output 1 4 5 2

explanation (1+2x)⋅(1+2x+ x 2 )=1+4x+5 x 2 +2 x 3 (1+2x)⋅(1+2x+x2)=1+4x+5×2+2×3 。 限制与约定 0≤n,m≤ 10 5 0≤n,m≤105 ,保证输入中的系数大于等于 0 0 且小于等于 9 9 。 时间限制: 1s 1s 蒟蒻我暂时只会搞多项式乘法? n-1次多项式A(x)与m-1次多项式B(x)相乘获得l=n+m-1次多项式c(x) 直接朴素做是n*m的复杂度 对于这题 显然不可做 考虑新学一种算法fft C(x)=A(x)*B(x)

Ci= \sum_{p=0}^{n-1}\sum_{q=0}^{m-1}[p+q==i] A_{p}*B_{q}

Ci= \sum_{p=0}^{n-1}\sum_{q=0}^{m-1}[p+q\equiv i (mod\ l)] A_{p}*B_{q}

已知一个式子 对于任意v均满足 如果需要知道这个式子首先需要知道复数的应用 例如欧拉公式

e^{i\pi}=1

\omega_l

表示l次单位复数根

[v\equiv 0(mod\ l)]=\frac{1}{l}*\sum_{k=0}^{l-1}\omega^{v*k}_{l}

对于

v\equiv 0(mod\ l)

显然可以知道 对于这种情况 是成立的 对于

v \not \equiv 0(mod\ l)

的情况 可以知道 对于原式是

\frac{1}{l}*\sum_{i=0}^{l-1} \omega_{l}^{i*v}

对于这个

\sum

我可以考虑等比数列搞出 化简之后就是

\frac{1-\omega_{l}^{l*v}}{1-\omega_{l}^{v}}=0

所以可以证明这个式子成立 带入原始式子

Ci= \sum_{p=0}^{n-1}\sum_{q=0}^{m-1}[p+q-i\equiv 0 (mod\ l)] A_{p}*B_{q}

Ci= \sum_{p=0}^{n-1}\sum_{q=0}^{m-1}(\frac{1}{l}*\sum_{k=0}^{l-1}\omega^{(p+q-i)*k}_{l})A_{p}*B_{q}

交换枚举对象

Ci= \frac{1}{l}*\sum_{k=0}^{l-1}\omega^{-i*k}_{l} (\sum_{p=0}^{n-1}\omega^{p*k}_{l}A_{p})*(\sum_{q=0}^{m-1}\omega^{q*k}*B_{q})

根据多项式定义后面的两部分可以分别表示为

\sum_{p=0}^{n-1}\omega^{p*k}_{l}A_{p}=A[\omega^{k}_{l}]

B同理 所以

ci=\frac{1}{l}*\sum_{k=0}^{l-1}\omega^{-i*k}_{l} *A[\omega^{k}_{l}]*B[\omega^{k}_{l}]

dk=A[\omega^{k}_{l}]*B[\omega^{k}_{l}]

显然如果我有办法快速求出A的所有点值那我可以采取同样的方法快速求出每个dk的值 相当于只是 带入的值变化了 如何快速球值这就需要我们选取的这个值即可 注意我们选择2n次复数根J即将n,m同时扩大到和他们最近的一个2n次幂的地方 如何快速求出A[x]即

\sum_{i=0}^{n-1} x^{i}*a_{i}

显然我可以针对下标划分成奇偶两种形式 设A0表示偶数次的项 A1表示奇数次的项

A0(x)=\sum_{i=0,i+=2}^{n-1}x^{i}*a_{i}

A0(x)=\sum_{i=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}x^{2i}*a_{2i}

di=a_{2i}

那么可以表示成设

D(x)=\sum_{i=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}x^{i}*d_{i}

那么显然可以知道

A0(x)=D(x)^{2}

同理我们去搞一下奇数次的项

A1(x)=\sum_{i=0,i+=2}^{n-1}x^{i}*a_{i}

A1(x)=x*\sum_{i=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}x^{2i}*a_{2i+1}

ei=a_{2i+1}

E(x)=\sum_{i=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}x^{i}*e_{2i}

A1(x)=x*E(x^{2})

所以

A(x)=A1(x)+A0(x)

当k<

\frac{l}{2}

A(\omega_{l}^{k})=A0(\omega_{l}^{k})+A1(\omega_{l}^{k})

A(\omega_{l}^{k})=D(\omega_{l}^{2k})+\omega_{l}^{k}*E(\omega_{l}^{2k})

A(\omega_{l}^{k})=D(\omega_{\frac{2}{l}}^{k})+\omega_{l}^{k}*E(\omega_{\frac{2}{l}}^{k})

同理获得当

k>=\frac{l}{2}

此时设定

k=k-\frac{l}{2}

A(\omega_{l}^{k+\frac{l}{2}})=D(\omega_{l}^{2k+l})+\omega_{l}^{k+\frac{l}{2}}*E(\omega_{l}^{2k+l})

此时和上面相同只不过

\omega_{l}^{\frac{l}{2}}

是-1所以要注意负号

递归版

 

迭代版

 

分类: fft

elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论