- 万年大坑终于填上了
原根的应用
单位复数根的局限
使用单位复数根进行快速傅里叶变换，总会产生精度误差
而当题目要求取模时，单位复数根就GG了
这时我们只能放弃单位复数根，去寻找新的东西
万幸的是，我们找到了原根，完美地解决了这个问题，或许这就是数学的美吧
单位复数根的替代
- 次数原根了解一下传送门
由费马小定理我们知道素数$G$满足$G^{p-1}\equiv 1 (mod p)$
所以我们取$w_n=G^{\frac{p-1}{n}}$，就能满足$w_n^n=G^{p-1} \equiv 1 (mod p)$
考虑在FFT中我们利用的单位复数根$\omega_n^k=\cos\frac{2\pi}{n}k+i\sin\frac{2\pi}{n}k$的那些性质
性质一：$\omega_n^k$互不相同，用于保证点值合法
而原根$G$满足$1,G,G^2,…,G^{p-1}$互不相同，满足该性质
性质二：消去引理$\omega_{2n}^{2k}=\omega_{n}{k}$，用于分治
而原根$G$满足$\omega_{2n}^{2k}=G^{\frac{(p-1)2k}{2n}}=G^{\frac{(p-1)k}{n}}=\omega_n^k$，满足该性质
性质三：$\omega_n^{k+\frac{n}{2}}=-\omega_n^k$，用于分治
而原根$G$满足$\omega_n^{\frac{p-1}{n}(k+\frac{n}{2})}=G^{\frac{(p-1)k}{n}}\times G^{\frac{p-1}{2}}$
而$G^{p-1} \equiv 1$，所以$G^{\frac{p-1}{2}}\equiv -1$（由于G是原根，+1值舍去），所以该性质成立
性质四：求和引理$\sum_{i=0}^{n-1}(\omega_{n}^{k})^i=0$
而原根$G$满足$\sum_{i=0}^{n-1}G^{\frac{(p-1)ki}{n}}=\frac{1-G^{(p-1)k}}{1-G^{\frac{(p-1)k}{n}}}=0$，满足该性质（等比数列求和）
综上所述，原根可以完美地代替单位复数根，作为点值进行FFT运算
我们把使用原根的这种运算称为快速数论变换，也就是NTT
NTT素数
我们注意到$w_n=G^{\frac{p-1}{n}}$中，$n$代表多项式的次数界，是$2$的整次幂
而$n|(p-1)$，这就要求$n=r*2^k+1$
我们最常见的就是$UOJ$模数$998244353=119\times 2^{23}+1$（原根G=3）
再额外记住两个$NTT$模数用于三模数$NTT$（后面会讲到）：
$1004535809=479\times 2^{21}+1$（原根G=3）
$2281701377=17\times 2^{27}+1$（原根G=3）
代码实现
实现技巧
我用的是mzx大爷的板子
具体来讲就是预处理所有要用到的原根
其中数组$wn[0][n]$表示$w_{2^n}$，$wn[1][n]$表示$wn[0][n]$的逆元，用于逆变换
参考代码
|
|
模数不符合要求的情况
三模数NTT
- 【COGS2294】释迦【传送门】
以此题为例，由于所给模数是23333333，显然不是一个NTT模数
假设我们选取了三个$NTT$模数$m_1,m_2,m_3$，并且计算出了在这三个模数意义下的答案$a_1,a_2,a_3$
那么我们就得到了三个同余方程：
$Ans \equiv a_1 (mod m_1)$
$Ans \equiv a_2 (mod m_2)$
$Ans \equiv a_3 (mod m_3)$
考虑使用中国剩余定理合并
由于卷积之后每个数达到了$10^{23}$的数量级，所以需要满足$m_1 m_2 m_3> 10^{23}$
由于$10^{23}>2^{64}$，所以直接合并会炸longlong，需要一些$tricky$
我们先用中国剩余定理合并前两个式子得到：
$Ans \equiv A(mod M)$
$Ans \equiv a_3(mod m_3)$
不妨设$Ans=KM+A=km_3+a_3$，我们可以在模$m_3$意义下求解：
$KM \equiv a_3-A(mod m_3)$
$K \equiv (a_3-A)\times M^{-1} (mod m_3)$
将$K$回带$Ans=KM+A$就可以求出$Ans$，然后对23333333取模即可
参考代码：
|
|
拆系数FFT
留坑……