【UOJ34】多项式乘法 Vol.2

UOJ模板题库T1

传说中的快速傅里叶变换

然而听说快速数论变换也可做就来学习一个(其实就是来学NTT的)

【学习NTT前请先学习FFT相关内容

一、原根

在FFT中,之所以能够实现\(nlogn\)的求值插值是因为\(n\)次单位复数根满足下面这个神奇的性质(即消去引理):

$$ω_{ak}^{bk}=ω_a^b$$

进而得到折半引理使得算法可以分治实现。

一个质数\(p\)的原根\(g\)是满足在模\(p\)意义下\(g\)的\(1\)到\(p-1\)次幂构成了\(1\)到\(p-1\)的一个排列的数。

我们令\(g_n=g^{\frac{p-1}{n}}\),则\(g_n\)等价于\(ω_n\)。

对于\(n\)次单位复数根满足的性质,\(g_n\)同样满足:

\(ω_n^n=1\)类比于\(g_n^n=g^{p-1}\equiv 1\pmod{p}\)

\(ω_{ak}^{bk}=ω_a^b\)类比于\(g_{ak}^{bk}=g^\frac{bk(p-1)}{ak}=g^\frac{b(p-1)}{a}=g_a^b\)

同样的折半引理也适用于它。

二、NTT

NTT适用于对一些形如\(p=c2^k+1\)的数取模,且\(2^k>n\)(当然也可以将不取模但结果不会超过某个范围视作取模)的多项式乘法问题。

这时只要将\(g_n\)当作FFT中的\(ω_n\)使用即可。

当然NTT使用的模数要满足有原根。

常见的NTT模数:

\(998244353=119\times 2^{23}+1\),原根为\(3\)。

\(1004535809=479\times 2^{21}+1\),原根为\(3\)。

\(15\times 2^{112}+1\),原根为\(11\)(感谢@r_64提供,不过这真的常用?)。

三、任意模数FFT

原来CRT就是中国剩余定理,吓死我了

然而听说不是把模数质因数分解又吓死我了

不过也有道理。质因子不一定有原根啊(如果都有的话也不是不可以用呀?)

取三个\(10^9\)级别且满足NTT要求的模数做NTT得到三个答案,再作死用CRT+高精度合并即可。

Update:原来正解不是CRT啊 吓死的可能是假我

令\(P_0=\sqrt{P}\),那么我们可以将每个数表示为\(kP_0+b\)。将每个多项式拆成\(k\)的一个多项式和\(b\)的一个多项式,四项分别相乘,最后再一起计算到答案中,就不会爆ll了。

四、附录

然后发现TMD我只会暴力求。

暴力很简单,挨个枚举\(g\)判断是否满足即可。

但【判断是否满足】是可以简化的。将\(p-1\)分解质因数,对于所有质因子\(q\),如果没有一个满足\(g^\frac{p-1}{q}\equiv 1\pmod{p}\),那么\(g\)是\(p\)的原根。(证明我不会)

所以我们可以很轻松地求出RG提供的模数的原根。

最后附上本题代码:

(听说常数更大然而这道题跑得比FFT还快?)

和模\(10^9+7\)(虽然没有用)的代码

4
说点什么

2 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
成员
LCF

好劲啊

成员
MasterJH5574

你才知道CRT = Chinese Remainder Theorem?

成员
LCF

%