前传及前置：多项式入门：快速傅里叶变换
求 ，不仅可以用快速傅里叶变换，还可以用快速数论变换 NTT。
首先引入快速数论变换的前置知识：
欧拉函数
一个数的欧拉函数 代表 的正整数中与 互质的数的数目。
它有一个性质是欧拉定理：若 互质，则 。
阶
若 互质，那么就记使 的最小正整数 称为 模 的阶，即 。
e.g. 若 ，根据 ，即可得到 。
原根及其性质
若 ，也就是当某个数模 的阶与 的欧拉函数相等时，我们就称 为模 的一个原根。
如果 是模 的一个原根，那么 在模 意义下两两不同。之后进入周期。
也就是假设 ，那么 以此类推。
那么它有什么性质呢（注意以下 的表述为在模 意义下，在 序列里面选择间隔相等的 个数，在这 个数里面的第 个，也就是 （此时））？
- 指数性：。这个是容易得出的，根据乘法、乘方运算性质可得。
- 周期性：。这个也是容易得出的，因为 。
- 对称性：。因为 ，又因为所有的 个 值都是互不相同的。所以 。即 。
- 折半性：。。
感觉是不是在哪里见过？
单位根有一些性质：
而 FFT 在运算的时候要求 ，也就是 必须是 的整数次幂，那么它也就有了以下几种特殊性质：
- 周期性：。也就是它其实是 个一循环的。
- 对称性：。因为这里的 它是 的整数次幂，所以可以证明这一点。就如上图的 和 。
- 折半性：。也比如上面的 和 。
——选自《多项式入门：快速傅里叶变换》
简直一模一样！
而我们的这个 NTT，就是和 FFT 思想相似，选取 个不同的原根来确定 次多项式。这个 还要是 的整数次幂。
现在我们要对 和 进行选择。
我们为了要多次二分，要让 为 的整数倍，那么模数 应该选形如 的质数。其中 应为奇质数，。
那么：比如我们天天都见得到的模数 ，它其实等于 ，它最多能被二分 次，也就是说，以它为模数的话，最终多项式的长度必须小于 。因为后面就不能将 进行 的整数次幂等分了。
因为 是质数，，所以 是两两不同的，于是我们从中选择对称的 个值。然后像 FFT 一样，二分。然后就做完了。
注意取模问题！
Code:
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
| typedef long long ll;
const ll mod = 998244353, g = 3;
ll ginv;
ll ksm(ll bas, ll x){
ll ans = 1;
while(x){
if(x&1) ans = ans * bas % mod;
bas = bas * bas % mod;
x >>= 1;
}
return ans;
}
ll a[N], b[N];
int r[N];
void change(ll A[], int n){
for(int i=0;i<n;i++)
r[i] = (r[i>>1]>>1) + ((i&1)*(n>>1));
for(int i=0;i<n;i++)
if(i<r[i]) swap(A[i], A[r[i]]);
}
void NTT(ll A[], int n, int op){
change(A, n);
for(int m=2;m<=n;m<<=1){
ll g1;
if(op==1) g1 = ksm(g, (mod-1)/(m));
else g1 = ksm(ginv, (mod-1)/(m));
for(int i=0;i<n;i+=m){
ll gk = 1;
for(int j=0;j<m/2;j++){
ll x = A[i+j], y = gk*A[i+j+m/2] % mod;
A[i+j] = (x+y)%mod, A[i+j+m/2] = (x-y+mod)%mod;
(gk *= g1) %= mod;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
ginv = ksm(g, mod-2);
int n, m;
n = read(), m = read();
for(int i=0;i<=n;i++) a[i] = read();
for(int i=0;i<=m;i++) b[i] = read();
int all = n+m, len = 1;
for(len = 1;len <= all; len <<= 1) ;
NTT(a, len, 1), NTT(b, len, 1);
for(int i=0;i<len;i++){
(a[i] *= b[i]) %= mod;
}
NTT(a, len, -1);
ll invlen = ksm(len, mod-2);
for(int i=0;i<=all;i++){
write(a[i] * invlen % mod, ' ');
}
return 0;
}
|
