# 快速数论变换(NTT)小结

## 原根

m是正整数，a是整数，若am的阶等于\phi(m)，则称a为模m的一个原根

• P为素数，假设一个数gP的原根，那么g^i \mod P (1<g<P,0<i<P)的结果两两不同

1 . 对于所有\omega_n ^ t (0 \leq t \leq n - 1)均不相同

2 .\omega_{2n} ^ {2k} = \omega_n ^ k

3 .\omega_n ^ { k + \frac{n}{2} } = -\omega_n ^ k

4 .1 + \omega_n ^ k + (\omega_n ^ k) ^ 2 + \dots + (\omega_n ^ k) ^ {n - 1} = 0

\omega_n \equiv g^\frac{p-1}{n} \mod p

p建议取998244353，它的原根为3

## 实现

NTT求卷积代码:

#include<cstdio>
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<21, stdin), p1 == p2) ? EOF : *p1++)
#define swap(x,y) x ^= y, y ^= x, x ^= y
#define LL long long
const int MAXN = 3 * 1e6 + 10, P = 998244353, G = 3, Gi = 332748118;
char buf[1<<21], *p1 = buf, *p2 = buf;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M, limit = 1, L, r[MAXN];
LL a[MAXN], b[MAXN];
inline LL fastpow(LL a, LL k) {
LL base = 1;
while(k) {
if(k & 1) base = (base * a ) % P;
a = (a * a) % P;
k >>= 1;
}
return base % P;
}
inline void NTT(LL *A, int type) {
for(int i = 0; i < limit; i++)
if(i < r[i]) swap(A[i], A[r[i]]);
for(int mid = 1; mid < limit; mid <<= 1) {
LL Wn = fastpow( type == 1 ? G : Gi , (P - 1) / (mid << 1));
for(int j = 0; j < limit; j += (mid << 1)) {
LL w = 1;
for(int k = 0; k < mid; k++, w = (w * Wn) % P) {
int x = A[j + k], y = w * A[j + k + mid] % P;
A[j + k] = (x + y) % P,
A[j + k + mid] = (x - y + P) % P;
}
}
}
}
int main() {
for(int i = 0; i <= N; i++) a[i] = (read() + P) % P;
for(int i = 0; i <= M; i++) b[i] = (read() + P) % P;
while(limit <= N + M) limit <<= 1, L++;
for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
NTT(a, 1);NTT(b, 1);
for(int i = 0; i < limit; i++) a[i] = (a[i] * b[i]) % P;
NTT(a, -1);
LL inv = fastpow(limit, P - 2);
for(int i = 0; i <= N + M; i++)
printf("%d ", (a[i] * inv) % P);
return 0;
}

1811 篇文章122 人订阅

0 条评论

## 相关文章

33450

### Spark 1.4为DataFrame新增的统计与数学函数

Spark一直都在快速地更新中，性能越来越快，功能越来越强大。我们既可以参与其中，也可以乐享其成。 目前，Spark 1.4版本在社区已经进入投票阶段，在Gi...

37370

21060

36480

### BZOJ 2038: [2009国家集训队]小Z的袜子(hose)【莫队算法裸题&&学习笔记】

2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec  Memory Limit: 259 MB Submit: 9...

31360

40460

56340

16230

23390

### 有向无环图检测

01 — Spark背景介绍 Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环...

49970