FFT | 3 | 数论变换NTT基础

FFT | 3 | 数论变换NTT基础

什么是 $NTT$

就是把把 $FFT$ 中所有的单位根换成了整数的单位根,也就是原根的 $n$ 次幂

通常用于求模意义下的多项式卷积

为什么要用 $NTT$

  • 保证精度
  • 能用来解决模意义下的卷积问题
  • 空间更小
  • 但速度不一定更优

前置知识

对于满足 $gcd(a,p)=1$ 的正整数对 $a,p$ ,若 $r$ 是使得 $a^r\equiv 1\pmod p$ 成立的最小整数,则称 $r$ 为 $a$ 模 $p$ 的阶

原根

若在正整数对 $a,p$ 中,$a$ 模 $p$ 的阶等于 $\phi(p)$ ,则称 $a$ 为 $p$ 的原根

原根有一个特殊的性质

若 $a$ 为 $p$ 的原根,则对于任意整数 $k;(1\le k<p)$ ,$\left(a^k\right)\mod p$ 的值两两不相同

$NTT$ 的单位根

现在设我们的原根为 $a$ ,模数为 $p$ ,那么我们现在的单位根就变成了 $\omega_n^k=a^{k(p-1)/n}$

我们来回顾一下 $FFT$ 中要求的单位根的性质

$$
(\omega_n^k)^t=w_n^{tk}\tag{1}
$$

易证

$$
\omega_n^k=\omega_{n/2}^{k/2}\tag{2}
$$

易证

$$
\omega_n^{j+k}=\omega_n^j\cdot\omega_n^k\tag{3}
$$

易证

$$
\omega_n^0=\omega_n^n=1+0i\\
\omega_n^{n/2}=-1+0i\tag{4}
$$

不易证,证不来

$$
w_n^{k+n/2}=-\omega_n^k\tag{5}
$$

证了上面一个就易证了,可惜我证不来


实现

貌似没什么好说的,把 $FFT$ 里面的单位根换了,再把除法用乘上逆元代替就好了

代码中用到了一个很常用的大质数和它的逆元:$998244353$ ,原根为 $3$ ,能够在保证很大的范围内不被模掉

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <cmath>

#define endl '\n'
#define IO(n) freopen(#n".in","r",stdin),freopen(#n".out","w",stdout)
#define USING_R(fn,n) n fn() {static n _R;static char _C;static bool _F;_F=0;_R=0;_C=GG();while((_C<'0'||_C>'9')&&_C!='-'&&_C!='\0')_C=GG();if(_C=='-')_F=1,_C=GG();while(_C>='0'&&_C<='9')_R=(_R<<3)+(_R<<1)+_C-'0',_C=GG();if (_F) _R=-_R;return _R;}
#define USING_F(bufsize) char FGC(){static char Buffer[bufsize],*st=NULL,*en=NULL;if(st==en){en=(st=Buffer)+fread(Buffer,1,bufsize,stdin);if(st==en) return EOF;}return *st++;};
#define USING_T(a) const char* __DATA=a;char TGC(){return *__DATA++;}
#define P(a) cout<<#a"="<<(a)<<endl
#define R Read()
#define GG getchar

#define nmax 10097155
#define MOD 998244353
#define G 3
#define sn(a,b) a^=b^=a^=b
const double PI=acos(-1);

USING_R(Read,int)
int f1[nmax],f2[nmax];
int pos[nmax];
int n,m;
int len;
int rev;
int ksm(long long x, int p) {
static long long ret;
ret=1;
while (p) {
if (p&1) ret=(ret*x)%MOD;
x=(x*x)%MOD;
p>>=1;
}
return ret;
}
inline void ntt(int* a, bool inv) {
register int i,j,k,q;
static int delta,w,x,y;
for (i=0;i<len;i++)
if (i<pos[i])
a[i]^=a[pos[i]]^=a[i]^=a[pos[i]];
for (i=1,q=2;i<len;i=q,q<<=1) {
delta=ksm(G,(MOD-1)/q);
if (inv) delta=ksm(delta,MOD-2); //delta变为(1/delta)
for (j=0;j<len;j+=q) {
w=1;
for (k=0;k<i;k++,w=(1LL*w*delta)%MOD) {
x=a[j+k],y=(1LL*a[i+j+k]*w)%MOD;
a[j+k]=(x+y)%MOD,a[i+j+k]=(x-y+MOD)%MOD;
}
}
}
if (inv)
for (i=0;i<len;i++) a[i]=(1LL*a[i]*rev)%MOD;
}
int main() {
n=R,m=R;
register int i,j;
for (i=0;i<=n;i++) f1[i]=R;
for (i=0;i<=m;i++) f2[i]=R;
i=j=m+n+1;
do {
len=i&(-i);
i&=~len;
} while (i);
if (len^j) len<<=1;
for (i=1;i<=len;i++) {
pos[i]=pos[i>>1]>>1;
if (i&1) pos[i]^=pos[1];
}
rev=ksm(len,MOD-2); //预处理len的逆元
ntt(f1,0),ntt(f2,0);
for (i=0;i<len;i++) f1[i]=(1LL*f1[i]*f2[i])%MOD;
ntt(f1,1);
for (i=0;i<j;i++) printf("%d ",f1[i]);
return 0;
}

任意模数的 $NTT$

使用多个大质数分别 $NTT$ 最后用 $CRT$ 合并即可,不过常数略大

一般取 $998244353,;1004535809,;469762049$ ,这三个数原根都为 $3$

例题

P4245 【模板】任意模数NTT

FFT | 3 | 数论变换NTT基础

https://mivik.gitee.io/2019/intro/ntt-basic/

作者

Mivik

发布于

2019-09-28

更新于

2021-05-31

许可协议

评论