多项式2·NTT以及任意模数NTT

$0x01\quad \rm{Preface}$

无特别说明,本文不区分$n$和$N$两种符号,均表示形式为$2^j(j \in \mathbb{N+})$的多项式长度(或者,次数)。

我们知道,对于$FFT​$而言,其得以优化成$\log​$的根本原因是找到了单位复根这个东西,可以方便处理+计算。而另一种方法则是在模意义下,利用原根的美妙性质,进行多项式卷积。

$\boldsymbol{NTT~\text{(Fast Number-Theoreti Transform)}}$,快速数论变换。在分析$NTT$是如何利用原根之前,需要先分析$FFT$是如何利用的单位复根$^{[1]}$:

  • $\omega_n^n = 1$。

  • $\omega_n^1,\omega_n^2, \omega_n^3\cdots\omega_n^{n-1}$是互不相同的,这样带入计算才能保证插出一个完整的$n$次多项式。

  • {$\omega_n^2$} = {$\omega_{\frac{n}{2}}^{2}​$},这使得问题规模可以在计算的时候减半。

  • $$
    \sum \limits _{k=0}^{n-1} (\omega_n^{j-i})^k =
    \begin{cases} 0 \quad i \neq j \newline n \quad i = j \newline \end{cases}
    $$

这样可以保证我们能够使用相同的方法进行逆变换。


首先,原根的基本定义:设$g$为$p$的一个原根,则满足:
$$
𝑔^{𝑝−1} \equiv 1(\mod p) \\
∀1≤𝑘<𝑝−1, 𝑔^𝑘 \not \equiv 1(\mod p)
$$
换句话说$g^0,g^1,g^2\cdots,g^{p-2} \quad (\bmod p)$ 是互不相同的数,满足性质二。

同时如果我们令$p-2$作为这个群的阶,那么$g^{p-1}$和$\omega_n^n$,其实就是等价的,只不过
$$
g^{p-1} \equiv1(\bmod~p) \ \omega_n^n=1
$$
而已。于是就满足性质一。

而对于性质三,我们先考虑一个转化。我们如果要将$g​$作为单位根的替代的话,就需要用到$g^{\frac{p-1}{N}}​$。换句话说,$N | (p-1)​$。那么我们便可以令$g_n^k \equiv g^{\frac{k(p-1)}{N}} (\bmod~p)​$,得到一个和单位根相似的形式。

那么接下来,因为$p​$是素数,所以在$g_n^n\equiv g^{\frac{N(p-1)}{N}}\equiv g^{p-1} \equiv 1 (\bmod ~p)​$的基础上,我们可以得到$g_{2n}^{n} \equiv1\quad\text{or}\quad \text{-1} (\bmod~ p)​$,那么平方之后性质三便显而易见;或者考虑另一种思路,我们根据刚才得出的、跟二次剩余有些相似的式子,可以得到以下结论:
$$
g_n^{\frac{n}{2}+k}=-g_n^k (\bmod~p)
$$
再结合显而易证的消去引理$g_n^k \equiv g_{jn}^{jk}$,我们可以很自然像$FFT$证明单位复根的折半性一样,证出这个结论。

至于性质四,证明的大体相似于单位单位复根。即:
$$
\sum\limits_{j =0}^{n-1}{(g_n^k)^j} \equiv \frac{(g_n^k)^n -1}{g_n^k -1} \Longrightarrow \frac{(g_n^n)^k -1}{g_n^k -1} \equiv \frac{(1)^k -1}{g_n^k -1} = 0
$$
而对于$n=k$的情况,不适用于普通的几何级数求和,所以直接就是$\sum 1 =n$ 。

$0x02\quad \rm{Codes}$

呃,于是NTT就完了。注意因为要保证$N | (p-1)$,且$N$是$2$的幂次,所以素数$p$一定要是$2^j+1$的形式。

至于求原根,不是本界探讨的内容。普通的NTT模数,原根可以背过;其余情况暴力求+验证即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int N, M, K, qaq ;
const int MAXN = 3000010 ;
LL A[MAXN], B[MAXN], Inv ;
const double Pi = acos(-1.0) ;
int i, j, k, l, Lim = 1, L, R[MAXN] ;
const int P = 998244353, G = 3, Gi = 332748118 ;

namespace IO{
const int ch_top=4e7+3;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
inline int read(){
while(*++now_r<'0');
register int x=*now_r-'0';
while(*++now_r>='0')x=x*10+*now_r-'0';
return x;
}
inline void write(int x){
static char st[20];static int top;
while(st[++top]='0'+x%10,x/=10);
while(*++now_w=st[top],--top);
*++now_w=' ';
}
}
inline LL expow(LL a, LL b){
register LL res = 1 ;
while (b){
if (b & 1) (res *= a) %= P ;
(a *= a) %= P, b >>= 1 ;
}
return res ;
}
void NTT(LL *J, int flag){
for(i = 0; i < Lim; i ++)
if(i < R[i]) swap(J[i], J[R[i]]) ;
for(j = 1; j < Lim; j <<= 1){
LL Gn = expow(flag == 1 ? G : Gi, (P - 1) / (j << 1)) ;
for(k = 0; k < Lim; k += (j << 1) ){
LL g = 1 ;
for(l = 0 ; l < j ; l ++, g = (g * Gn) % P){
LL Nx = J[k + l], Ny = g * J[k + j + l] % P ;
J[k + l] = (Nx + Ny) % P, J[k + j + l] = (Nx - Ny + P) % P ;
}
}
}
}
using namespace IO ;
int main(){
fread(ch,1,ch_top,stdin);
N = read(), M = read() ;
while(Lim <= N + M) Lim <<= 1, L ++ ;
for(i = 0; i <= N; i ++) A[i] = (read() + P) % P ;
for(i = 0; i <= M; i ++) B[i] = (read() + P) % P ;
for(i = 0; i < Lim; i ++ ) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1)) ;
NTT(A, 1), NTT(B, 1);for(i = 0; i <= Lim; i ++) A[i] = (A[i] * B[i]) % P ; Inv = expow(Lim, P - 2) ;
NTT(A, -1) ; for(i = 0; i <= N + M; i ++) write((long long) (A[i] * Inv + P) % P) ; fwrite(ch, 1, now_w - ch, stdout) ; return 0 ;
}

其中Gi表示$998244353$的原根的逆元。

$0x03\quad \rm{Extending}$

接上节内容,$NTT$本质上是只能处理“$NTT$模数($p=2^k+1$)”。但是当我们需要对其进行任意模数取模时,就需要我们用$CRT$合并。

先咕着qwq……

-------------本文结束感谢您的阅读-------------