这是一道模板题。

给你两个多项式,请输出乘起来后的多项式。

输入格式

第一行两个整数

n

m

,分别表示两个多项式的次数。

第二行

n+1

个整数,表示第一个多项式的

0

n

次项系数。

第三行

m+1

个整数,表示第二个多项式的

0

m

次项系数。

输出格式

一行

n+m+1

个整数,表示乘起来后的多项式的

0

n+m

次项系数。

样例一

input

output

explanation

(1+2x)(1+2x+x2)=1+4x+5x2+2x3

限制与约定

0n,m105

,保证输入中的系数大于等于

0

且小于等于

9

时间限制

1s

空间限制

ntt的诞生是为了解决 fft的单位复数根的精度误差

为了实现ntt我们需要找到一个东西使得他和fft里的w相同作用的东西

w有什么作用


  1. ωnn=1


  2. ωn0,ωn1,,ωnn1

    是互不相同的,这样带入计算出来的点值才可以用来还原出系数


  3. ωn2=ωn2,ωnn2+k=ωnk

    ,这使得在按照指数奇偶分类之后能够把带入的值也减半使得问题规模能够减半

  4. k=0n1(ωnji)k={0,   ijn,   i=j

    这点保证了能够使用相同的方法进行逆变换得到系数表示现在我们要在数论中寻找满足这三个性质的数,首先来介绍原根的概念,根据费马定理我们知道,对于一个素数

    p

    ,有下面这样的关系

    ap11(modp)

    这一点和单位根

    ω

    十分相似,

    p

    原根

    g

    定义为使得

    g0,g1,,gp2(modp)

    互不相同的数

    如果我们取素数

    p=k2n+1

    ,并且找到它的原根

    g

    ,然后我们令

    gngk(modp)

    ,这样就可以使得

    gn0,gn1,,gnn1(modp)

    互不相同,并且

    gnn1(modp)

    ,这便满足了性质一和性质二

    由于

    p

    是素数,并且

    gnn1modp

    ,这样

    gnn2modp

    必然是

    1

    1

    ,再根据

    gk

    互不相同这个特点,所以

    gnn21(modp)

    ,满足性质三

    对于性质四,和前面一样也可以验证是满足的,因此再 FNT 中,我们可以用原根替代单位根,这里已经有了一些数

    p

    及其原根,可以满足大部分需求

做这道题的时候用到的原根是3 在模数是998244353的情况下 所以在进行idft的时候直接写成mod-1-(mod-1)/(i<<1)即可 避免了再用快速幂进行计算的常数

资料借鉴于:http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform#i-15

 

分类: ntt

elijahqi

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

发表评论