学习笔记第三十八节：NTT，MTT，多项式求逆

2019-04-14 18:03发布

站内文章 / 模拟电子
17919 0 1523

正题

    NTT

      假设给出两个多项式，求他们的傅里叶卷积是及其简单的。       但是如果这两个多项式的值域为P，那么在运算的过程中，某一位的最大值是P^2n*limit，因为FFT本身自带一个limit。       所以当n<=limit<=4*10^5的时候，P<=10^9，很明显会爆long double.       通常这类问题他还会教你mod一个质数。      怎么做？       首先考虑FFT中的omega_n替换成q，可以使得sum_{k=0}^{n-1} q^{tk}=egin{Bmatrix} 0,n ot mid t\ n,nmid t end{Bmatrix}。       考虑模mod意义下原根a，因为原根a的阶<a>=varphi(mod)=mod-1。       所以不存在一个k< <a>，使得a^kequiv 1 (mod mod)。       q就显然等于a^{frac{mod-1}{n}}。因为只有这样，才能使得它有上面那个性质，而且和omega_n的性质相似。       当做idft的时候，就使q=(a^{frac{mod-1}{n}})^{-1}就可以了。       所以这个质数要拥有的性质是mod=2^q*l+1，而且这个q要尽量大，至少2^q>=limit。

    MTT

       那么当这个不是一个质数，或者没有NTT模数的性质呢？        考虑我们是因为什么才使用NTT的？没错，是因为它的乘积太大了。        FFT怎么避免这种问题？        拆分FFT（MTT）        我们对第一个多项式的每一项拆成a*sqrt{mod}+b的形式，对于第二多项式的每一项拆成c*sqrt{mod}+d的形式。        所以：ans=x*y=(a*c)mod+(a*d+b*c)sqrt{mod}+b*d。        我们做四次多项式乘法然后合并就可以了。可以知道，现在FFT过程中的最大值可能超过10^{18}，所以采用long double进行存储就可以了，对某些数据比较水的直接double即可。

    多项式求逆

      再讲一下多项式求逆。       就是已知一个多项式P，要找到一个G，使得P*Gequiv 1 (mod x^n)。       mod x^n的意思就是把第n位和后面砍掉。       使得这两个多项式相乘mod一个数之后，砍掉第n位以后的数位只有常数项剩下一个1.       假设我们已知P*Hequiv 1(mod x^{left lceil frac{n}{2} ight ceil})。       明显P*Gequiv 1(mod x^{left lceil frac{n}{2} ight ceil})       那么根据多项式的分配律，我们知道P*(H-G)equiv 0 (mod x^{left lceil frac{n}{2} ight ceil})。       接着，因为P不为0，所以H-Gequiv 0({mod x^{left lceil frac{n}{2} ight ceil}})       所以，我们知道(H-G)的第0项到第left lceil frac{n}{2} ight ceil-1项，都为0.       两边同时平方，就可以得到(H-G)^2equiv0(mod x^n)       因为平方之后的0 o n-1项，必定为0。考虑第i项从(0,i),(1,i-1)...(i,0)转移过来，就可以知道转移到0 o n-1项的二元组必定有一个位置<=left lceil frac{n}{2} ight ceil-1，证毕。       展开之后，乘上F可以得到H^2F+G^2F-2HGFequiv 0(mod x^n)。       又因为G*Fequiv 1(mod x^n)       可以得到H^2F+G-2Hequiv 0(mod x^n)。       移项就可以得到Gequiv2H-H^2F(mod x^n)。       H^2F用FFT，MTT，或者NTT求就可以了。       是不是加强版都是这样。       现在我们只需要递归就可以了，直到n=1的时候，直接令G[0]=F[0]^{-1}就可以了。

   那么，什么情况下一个多项式一定有逆呢？

      1.首先当P的第一位肯定不为0，用因为第0项只能由两个第0项转移过来，相乘之后肯定为0，而不为1.       2.P的第0项一定与模数互质，要么常数项的逆元都没法求。       3.其他的随意。

热门文章