
FFT 与 NTT 算法笔记
多项式乘法与点值表示
设两个多项式分别有 、 个系数:
将乘积展开并按次数合并,得到
这就是线性卷积。直接枚举每一对系数需要 时间。
若改为记录多项式在若干点上的取值,则在每个点 上都有
乘积点值可以通过逐项相乘得到。用点值计算多项式乘法,需要快速完成系数表示与点值表示之间的转换。MIT 6.046J FFT 讲义
次数小于 的多项式由 个互不相同的点值唯一确定。证明:若 、 在这些点取值相同,则 有至少 个根;非零多项式的根数不超过次数,而 ,所以 。因此,只要选取 个不同的点,就能从乘积点值恢复完整系数。
FFT 的推导
复数与单位根
复数写作 ,其中 。乘法为
单位圆上的点可以表示为 。由三角函数的和角公式,
因而乘法对应角度相加,乘方对应角度成倍增加。
求方程 的根。将 写为 ,由 得 ,由 是 的整数倍得
定义
全部 次单位根为 。若 ,则 ,等价于 ;所以这些根两两不同,且 的阶恰为 。
以下采用 的变换长度。对偶数 ,单位根有三条性质。
周期性:
相隔半圈取相反数:
平方后成为下一层单位根:
特别地, 与 的平方相同。全部 个单位根平方后,恰好得到 个单位根,每个出现两次;这使规模为 的求值问题能够递归到规模为 的求值问题。
离散傅里叶变换的定义
把系数数组补零到 项,令
在全部 次单位根上求值,得到离散傅里叶变换(DFT):
本文约定正变换使用正指数。每个点值直接计算需要 时间,全部点值需要 时间。FFT 利用单位根之间的关系,以 时间计算同一组点值。
奇偶拆分
将偶数下标和奇数下标分别组成两个多项式:
由指数 与 的区别,
求 在 上的值,只需知道 、 在 上的值。两个子多项式的系数个数与所需点值个数都减半,因而可继续采用同一拆分。到 时,多项式为常数,唯一点值就是 。
长度为 时,递归中各组包含的原数组元素如下。

蝶形合并的推导
设已经完成两个长度为 的子变换:
将 代入奇偶拆分式,由 得
还需计算另一个点 。它与 互为相反数,而
所以两个子多项式仍取相同的点值,奇数部分的外部因子变号:
合并公式为
每对输入 计算一次 ,再通过一加一减得到两个点值; 对输入恰好给出全部 个结果。
位逆序与按层合并
递归时先取偶数下标,再取奇数下标。设原下标的二进制表示为
第一层按 分组,第二层按 分组,依次直到 。叶子从左到右排列时,第一次分组决定叶子位置的最高位,第二次分组决定次高位,因此原下标 的叶子位置为
例如 时,下标 位逆序后为 ,所以 位于叶子序列的第 个位置(从 开始)。完整叶子顺序为
先按位逆序重排,递归树中的每个子问题就占据连续区间。从底层向上依次合并长度为 的区间,得到迭代变换。每层使用该层长度对应的单位根 ;长度为 的子变换,其定义中本来就使用 次单位根。
每层各子问题的长度总和为 ,合并工作量为 。共有 层,因此
采用原地迭代时,系数与点值复用同一数组,所需存储空间为 。
单位根求和与逆变换
对任意整数 ,考虑
若 ,每一项都为 ,于是 。若 ,令 ,则 且 ,由等比数列求和,
因此
这个求和关系可以把正变换中的各个系数分离。固定待恢复的下标 ,把正变换代入负指数求和:
由于 ,条件 仅在 时成立。求和后只有 保留,因此除以 即可恢复 。
逆变换公式为
仍是阶为 的单位根,具有同样的周期性、半圈变号与平方折半性质。因此,对点值数组使用负角度的单位根执行同样的分治,最后将每项除以 ,就得到原系数。逆变换的时间复杂度同样为 。
NTT 的推导
素数模数下的运算
NTT 在有限域 中进行,本文取素数 ,以 表示域元素。加法、减法和乘法都对 取模。下文 NTT 公式中的等号均表示 内的相等,即对应整数模 同余。
每个非零元素都有乘法逆元。对 ,因为 为素数,,所以乘以 会把全部非零余数重新排列。比较这些余数的乘积,有
乘积非零,可以约去,得到费马小定理及逆元公式:
这使等比数列求和中的除法,以及逆变换末尾的归一化,都能在模意义下完成。
原根与变换长度
一个非零元素的阶,是使其幂等于 的最小正整数。模素数 的原根 的阶为 ,因而
恰好遍历全部非零余数。
原根存在可以由有限域中多项式的根数说明。设全部非零元素的阶的最小公倍数为 。对 的素因数分解中的每个素数幂 ,选取一个阶中含有 的元素;若其阶为 且 ,取它的 次幂就得到阶为 的元素。将不同素数对应的元素相乘,得到阶为 的元素:这些元素的阶两两互质,乘积的阶等于各阶之积,因为相应子群的交集只有单位元。
另一方面,每个非零元素都是 的根,故 ;由费马小定理,每个元素的阶均整除 ,故 。于是 ,上述乘积就是一个原根。
要进行长度为 的变换,需要一个阶恰为 的元素。它的阶必须整除 ,所以要求
满足该条件时,定义
验证其阶:一方面
另一方面,若 ,由 的阶为 得
等价于 。因此 的阶恰为 ,且 两两不同。
取 时,模数通常写作 ,其中 为奇数。支持的二次幂长度满足 。例如
且 是该模数的原根,因此支持的最大二次幂长度为 。ACL 的原根实现
检查非零候选 是否为原根时,只需对 的每个不同素因子 验证
若 的阶为真因子 ,则整数 含有某个素因子 ,从而 ,对应幂会等于 ;反之,任一这样的幂等于 ,都说明阶小于 。
模意义下的单位根性质
对于偶数长度 ,必有奇素数模数 。周期性直接来自 :
令 ,则 ,即
域中没有零因子,所以 或 。由于 的阶为 ,不能有 ,故
对下一层长度,用同一个原根定义 ,于是
从而
这里的 表示余数 ,半圈变号由域中方程 的两个解导出。
NTT 正变换与蝶形合并
把系数视为 中的元素,定义正变换
同样按下标奇偶性定义
是多项式恒等式,在有限域中仍成立。记两个子变换为
对 ,展开完整变换并使用折半性质:
把 替换为 。子变换中的取值点不变,因为
奇数部分的因子变号,因为 。于是
递归终点仍是 时的常数多项式。每层 次模运算,共 层,故正变换需要 时间。位逆序由系数的奇偶拆分决定,与使用复数还是有限域无关,因此仍可按同一叶子顺序进行原地迭代。
NTT 逆变换的推导
有限域中的单位根也满足求和关系。若 ,
若 ,令 ,则 ,所以 非零且可逆,得到
因此
由于 ,有 ,所以 在模 下非零,逆元 存在。将正变换代入:
故逆变换为
逆单位根可以从原根逆元构造:
对点值数组用 生成各层单位根,执行同样的蝶形合并,再把每一项乘以 ,就得到原系数。
小模数例子
取 、。由于 ,而 , 的阶为 ,是原根。长度为 的单位根为
对系数 ,偶数与奇数下标数组分别是 、。由于 ,两个子变换为
在模 下合并:
所以完整点值数组为 。这里按原下标顺序存放结果,而计算过程中按成对点值合并。
逆单位根为 ,归一化因子为 。例如恢复下标 的系数:
此例中的全部等式均在 内成立。
由变换得到卷积
点值相乘为什么得到卷积
对 FFT 取 ,对 NTT 取 。将两个数组补零到相同长度 ,并记其正变换为 、。逐点相乘后,
对这些乘积点值做逆变换。复数域中的 表示 ;有限域中表示模逆元。恢复出的第 项()为
最后一步来自单位根求和:只有 的项保留。因此,长度为 的变换直接给出长度为 的循环卷积。
线性卷积为什么需要补零
原数组仅在 、 时非零,所以所有有效次数满足
若选取 ,这些次数均小于 。此时对 ,条件 等价于 ,从而
若长度不足,则次数 、 等位置的系数会累加到同一项。从多项式看,单位根满足 ,变换结果只能区分模 后的多项式:
因而需要完整线性卷积时,选取不小于 的最小二次幂 ;需要循环卷积时,则利用这一折叠关系。例如模 的卷积可先求普通乘积,再将次数按模 合并。
NTT 还必须满足 。ACL 的模数卷积接口也要求素数模数及足够大的二次幂因子。ACL 卷积文档
计算量与数值结果
完整卷积包含两次正变换、一次逐点相乘、一次逆变换,总时间为 ,采用原地迭代时空间为 。
FFT 的上述等式在复数域内精确成立;浮点实现会产生舍入误差。若原系数为整数,只有当恢复值与真实整数之间的误差小于 时,四舍五入才保证正确,系数范围和变换长度会影响这一误差。
NTT 的运算给出精确的模 卷积系数。单个模数只确定余数;需要其他模数下的结果或普通整数系数时,可以使用多个 NTT 模数与 CRT,并满足整数恢复的范围条件。下文三份源代码均执行 NTT,其中前两份将变换函数命名为 fft。
Luogu P4245:任意模数多项式乘法
题目重述
给出两个多项式及目标模数 ,输出它们相乘后各项系数对 取模的结果。目标模数不一定支持所需长度的 NTT。
关键观察
代码分别在 、、 下做 NTT。记三次卷积得到的第 项余数为 ,令 ,,并令 ,则 CRT 重建为
解析
代码先把两个多项式补零至足够大的二次幂长度,再对三个 NTT 模数分别执行卷积。最后用 CRT 恢复普通整数系数,并对目标模数 取模。所有中间合并使用 __int128,避免乘积溢出。
CRT 只能唯一恢复区间 中的整数。若原系数均在 ,则单个卷积系数满足
其中 是两个输入的系数个数。恢复普通整数系数要求这一上界严格小于 。三模数共同支持的二次幂长度受 限制,最大为 。
总时间复杂度为 ,空间复杂度为 ;三组模数只增加常数倍开销。
代码
源代码文件:luogu/P4245.cpp。
#include <bits/stdc++.h>#define ll long long#define pr pair<ll, ll>#define tii tuple<int, int, int>#define tll tuple<ll, ll, ll>#define sp << ' ' <<#define inf 0x3f3f3f3f3f3f3f3f#define N 100005#define lc p << 1#define rc p << 1 | 1#define ll __int128using namespace std;
int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); auto qp = [&](ll x, ll k, ll MOD) { ll res = 1; while (k) { if (k & 1) res = (res * x) % MOD; x = (x * x) % MOD; k >>= 1; } return res; }; auto multi = [&](vector<ll> a, vector<ll> b, ll MOD) { auto n = a.size(); const ll g = 3, gi = qp(3, MOD - 2, MOD); auto fft = [&](vector<ll> &a, ll g) { int n = a.size(); vector<int> aim(n, 0); for (int i = 1; i < n; i++) { aim[i] = (aim[i >> 1] >> 1) + (i & 1) * (n >> 1); } for (int i = 0; i < n; i++) { if (i < aim[i]) swap(a[i], a[aim[i]]); } for (int len = 2; len <= n; len <<= 1) { for (int left = 0; left < n; left += len) { ll gk = 1; ll g1 = qp(g, (MOD - 1) / len, MOD); for (int j = 0; j < len / 2; j++) { ll x = a[left + j], y = a[left + j + len / 2] * gk % MOD; a[left + j] = (x + y) % MOD, a[left + j + len / 2] = (x - y + MOD) % MOD; gk = (gk * g1) % MOD; } } } }; fft(a, g); fft(b, g); vector<ll> res(n, 0); for (int i = 0; i < n; i++) { res[i] = a[i] * b[i] % MOD; } fft(res, gi); auto inv = qp(n, MOD - 2, MOD); for (int i = 0; i < n; i++) { res[i] = (res[i] * inv) % MOD; } return std::move(res); }; auto solve = [&]() { long long n, m, p; cin >> n >> m >> p; vector<ll> a(n + 1, 0); vector<ll> b(m + 1, 0); for (int i = 0; i <= n; i++) { long long x; cin >> x; a[i] = x; } for (int i = 0; i <= m; i++) { long long x; cin >> x; b[i] = x; } for (m = n + m, n = 1; n <= m; n <<= 1) ; a.resize(n, 0); b.resize(n, 0); const ll p1 = 998244353; const ll p2 = 1004535809; const ll p3 = 469762049; ll product = (ll)p1 * p2 * p3; ll M1 = product / p1; ll M2 = product / p2; ll M3 = product / p3; ll t1 = qp((ll)(M1 % p1), p1 - 2, p1); ll t2 = qp((ll)(M2 % p2), p2 - 2, p2); ll t3 = qp((ll)(M3 % p3), p3 - 2, p3); auto r1 = multi(a, b, p1); auto r2 = multi(a, b, p2); auto r3 = multi(a, b, p3); for (int k = 0; k <= m; k++) { ll C = ((ll)r1[k] * M1 * t1 + (ll)r2[k] * M2 * t2 + (ll)r3[k] * M3 * t3) % product;
cout << (long long)(C % p) << ' '; } };
solve(); return 0;}AtCoder practice2 F:固定模数卷积
题目重述
给出两个系数数组,计算它们在模 下的线性卷积,并按次数递增输出系数。
关键观察
,原根为 ,因而支持不超过 的二次幂长度 NTT。代码中的 fft 函数执行 NTT。
解析
程序读取两个数组后补零到不小于输出系数个数的最小二次幂,分别做正变换,再逐点相乘。逆变换使用 ,随后乘 ,输出前 项。复杂度为 ,空间复杂度为 。
代码
源代码文件:atcoder/practice2/f.cpp。
#include <bits/stdc++.h>#define ll long long#define pr pair<ll, ll>#define tii tuple<int, int, int>#define tll tuple<ll, ll, ll>#define sp << ' ' <<#define inf 0x3f3f3f3f3f3f3f3f#define N 100005#define M 1000005#define lc p << 1#define rc p << 1 | 1using namespace std;const ll MOD = 998244353;int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); auto qp = [&](ll x, ll k) { ll res = 1; while (k) { if (k & 1) res = (res * x) % MOD; x = (x * x) % MOD; k >>= 1; } return res; }; const ll g = 3, gi = qp(3, MOD - 2); auto fft = [&](vector<ll> &a, ll g) { int n = a.size(); vector<int> aim(n, 0); for (int i = 1; i < n; i++) { aim[i] = (aim[i >> 1] >> 1) + (i & 1) * (n >> 1); } for (int i = 0; i < n; i++) { if (i < aim[i]) swap(a[i], a[aim[i]]); } for (int len = 2; len <= n; len <<= 1) { for (int left = 0; left < n; left += len) { ll gk = 1; ll g1 = qp(g, (MOD - 1) / len); for (int j = 0; j < len / 2; j++) { ll x = a[left + j], y = a[left + j + len / 2] * gk % MOD; a[left + j] = (x + y) % MOD, a[left + j + len / 2] = (x - y + MOD) % MOD; gk = (gk * g1) % MOD; } } } }; auto solve = [&]() { ll n, m; cin >> n >> m; n--, m--; vector<ll> a(n + 1, 0); vector<ll> b(m + 1, 0); for (int i = 0; i <= n; i++) cin >> a[i]; for (int i = 0; i <= m; i++) cin >> b[i]; for (m = n + m, n = 1; n <= m; n <<= 1) ; a.resize(n, 0); b.resize(n, 0); fft(a, g); fft(b, g); vector<ll> res(n, 0); for (int i = 0; i < n; i++) { res[i] = a[i] * b[i] % MOD; } fft(res, gi); auto inv = qp(n, MOD - 2); for (int i = 0; i <= m; i++) { cout << (res[i] * inv) % MOD << ' '; } };
solve(); return 0;}2023 ICPC 西安区域赛 F:An Easy Counting Problem
题目重述
给定整数 、素数 和非零剩余类 ,求满足
的整数对 数量,答案对 取模。约束为 、、; 以二进制字符串给出。原题:2023 ICPC 西安区域赛 F
关键观察
将 写成 位的 进制数,不足的位补零:
则
当 为素数时, 在 时均能被 整除,故 。于是
比较 的系数即得 Lucas 定理。各因子的局部次数小于 ,因此不产生数位进位。
若某位 ,该位组合数为零,整个乘积为零,与 矛盾。若各位均满足 ,则 ;局部组合数的分子、分母都由小于 的正整数相乘,所以其模 余数非零。合法整数对因此与 组满足局部条件的数位对一一对应,答案取决于这些组合数余数的乘积。
取模 的原根 ,令 。单个数位产生余数 的方案数为
合并两段数位时,余数满足乘法关系,所以频数转移为
因为 ,按离散对数重新排列余数后,下标转移成为模 的加法。定义
则所求答案为
组合数及余数乘法在模 下计算;方案数及 NTT 运算在模 下计算。代码中的 root 是模 的原根 ,g = 3 是模 的 NTT 原根。
解析
每个数位的余数分布都相同,因而需要计算 在模 下的 次幂。二进制快速幂需要 次循环卷积,其中 为 的二进制长度。
程序先用 Pascal 递推计算 c[i][j],此处对 取模。枚举 ,将每项计入 base.s[rev[c[i][j]]],其中 rev[v] 存储 。
poly::operator* 使用模 的 NTT 计算两个长度为 的数组的线性卷积。设结果为 ,由于 ,循环卷积需要折叠为
两个输入的次数都小于 ,乘积次数至多 ,因此每项最多折叠一次。代码先完成逆变换及乘 的归一化,再把第 项加回第 项,最后保留前 项。
qp_ 从二进制字符串末尾向前读取,维护当前底数与累积结果。初始结果是常数多项式 ;当前位为一时乘入底数,每处理一位就将底数平方。全部数位处理完后,res.s[rev[x]] 即为答案。
设二进制串长度为 ,代码选取不小于 的最小二次幂 。由 可知 ,且 。Pascal 表与逐候选原根搜索的预处理耗时至多 ;快速幂耗时 。总时间复杂度为 ,空间复杂度为 ;其中平方级空间来自代码保存的完整 Pascal 表。
代码
源代码文件:reginonals/23xian/f.cpp。
#include <bits/extc++.h>#include <bits/stdc++.h>#define ll long long#define pr pair<ll, ll>#define tii tuple<int, int, int>#define tll tuple<ll, ll, ll>#define sp << ' ' <<#define inf 0x3f3f3f3f3f3f3f3f#define N 100005#define M 1000005#define lc p << 1#define rc p << 1 | 1using namespace std;using namespace __gnu_pbds;ll p, x;string k;const ll MOD = 998244353;auto qp = [](ll x, ll k) { ll res = 1; while (k) { if (k & 1) res = (res * x) % MOD; x = (x * x) % MOD; k >>= 1; } return res;};const ll g = 3, gi = qp(3, MOD - 2);int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
auto solve = [&]() { cin >> k >> p >> x; class poly { public: vector<ll> s; poly() { s.assign(p - 1, 0); s[0] = 1; } poly(vector<ll> &&a) noexcept : s(std::move(a)){}; static void ntt(vector<ll> &a, ll g) { int n = a.size(); vector<ll> aim(a.size(), 0); for (int i = 1; i < n; i++) { aim[i] = (aim[i >> 1] >> 1) + (i & 1) * (n >> 1); } for (int i = 0; i < n; i++) { if (i < aim[i]) swap(a[i], a[aim[i]]); } for (int len = 2; len <= n; len <<= 1) { ll g1 = qp(g, (MOD - 1) / len); for (int left = 0; left < n; left += len) { ll gk = 1; for (int j = 0; j < len / 2; j++) { ll x = a[left + j], y = a[left + j + len / 2] * gk % MOD; a[left + j] = (x + y) % MOD, a[left + j + len / 2] = (x - y + MOD) % MOD; gk = gk * g1 % MOD; } } } } poly operator*(const poly &oth) const { vector<ll> a = s; vector<ll> b = oth.s; auto ori = a.size(); auto n = a.size(), m = b.size(); for (m = n + m, n = 1; n < m; n <<= 1) ; a.resize(n, 0); b.resize(n, 0); ntt(a, g); ntt(b, g); for (int i = 0; i < n; i++) { a[i] = a[i] * b[i] % MOD; } ntt(a, gi); auto inv = qp(n, MOD - 2); for (int i = 0; i < ori; i++) { a[i] = a[i] * inv % MOD, a[i + ori] = a[i + ori] * inv % MOD; a[i] = (a[i] + a[i + ori]) % MOD; } a.resize(ori); return {std::move(a)}; }; }; auto find_root = [&](ll p) { if (p == 2) return 1; for (int i = 2; i < p; i++) { auto x = i; for (int j = 1, x = i; j < p - 1; j++, x = x * i % p) { if (x == 1) goto ca; } return i; ca:; } }; auto root = find_root(p); vector<ll> rev(p + 10, 0); for (int i = 1, cnt = 0; cnt < p - 1; cnt++, i = i * root % p) { rev[i] = cnt; } vector<vector<ll>> c(p + 5, vector<ll>(p + 5, 0)); auto init = [&]() { c[0][0] = 1; for (int i = 1; i < p; i++) { c[i][0] = 1, c[i][i] = 1; for (int j = 1; j < i; j++) { c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % p; } } }; init(); poly base; base.s[0] = 0; for (int i = 0; i < p; i++) { for (int j = 0; j <= i; j++) { base.s[rev[c[i][j]]]++; } } auto qp_ = [&](poly x, string &k) { poly res; while (k.size()) { if (k.back() == '1') res = (res * x); x = (x * x); k.pop_back(); } return res; }; auto res = qp_(base, k); cout << res.s[rev[x]]; };
solve(); return 0;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 0 天
部分内容可能已过时