把十进制大数看成以 10 为底的多项式,用 FFT 在 O(n log n) 内求系数卷积,再从低位到高位统一进位得到乘积。
OJ: roj
题目 ID: 2128
难度:提高
标签:高精度FFT多项式python
创建: 2026-10-08 07:50
更新: 2026-10-08 07:50
形式化题目
给定两个十进制正整数
把
其中
换句话说,先求两个数位序列的卷积 0。
正解
思路
朴素做法及其瓶颈。 直接按竖式模拟:
再统一进位。循环体只有一次乘法一次加法,常数极小,但次数是
瓶颈非常明确:付出的代价是「位数 × 位数」,而这个乘积里绝大部分是重复的相位组合。
把视角从"数字"换成"多项式",就会看到
两个多项式相乘需要
这一步只要
为什么用 FFT 而不是别的。 Karatsuba 是
远小于 double 的 53 位尾数能精确表示的连续整数上界(此时仍在 round 抹平,不会出现错位。
长度取多少。 卷积长度是
算法流程(5 步)。
- 逆序读入两个数位串,把
、 填进复数数组 、 的实部,虚部置 0。 - 计算
,预处理 长的位反转置换表 rev。 - 对
、 各做一次正向 FFT,得到两组点值。 - 逐点相乘
,再对 做一次逆变换(IFFT), 逆变换里顺带除以 ,得到的就是卷积系数 。 - 从
起做十进制进位: cur = round(fa[k]) + carry,写下cur % 10,carry = cur / 10;进位链走完后剥掉高位多余的零,逆序输出。
为什么迭代式 FFT 而不是递归。 递归版每层要复制数组,len 从 2 倍增到
一个实现细节:本题的卷积结果(
这个文档的思路可信度说明。 本题素材源自带数据生成脚本(data.py),
说明测试数据是自造的、题面按《信息学奥赛一本通》第一章重建,与官方原题页可能略有差异;
其中第 2 组数据含 0 \times$ 大数 $= 0$,00000001` 当作
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 07:50
# update_at: 2026-10-08 07:50
import sys
DIGITS_LIMIT = 500000 # 200000 位的乘数、400000 位的积,都要超过 CPython 默认的 4300
def solve() -> None:
"""读入两个大整数并输出乘积:十进制串 → int → 相乘,交给 CPython 的 C 层大整数乘法。"""
# CPython 3.11+ 默认禁止超过 4300 位的十进制串与 int 互转,这里按数据上界放宽
sys.set_int_max_str_digits(DIGITS_LIMIT)
# 输入恰好两个数:直接解包,不用手算偏移,也不用 iter/next 的求值顺序陷阱
a, b = map(int, sys.stdin.buffer.read().split())
# 前导零、单独的 "0" 都由 int() 按数值语义吸收,结果直接输出十进制即可
sys.stdout.write(str(a * b) + "\n")
if __name__ == "__main__":
solve()C++ 版(FFT 正解):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 07:50
* update_at: 2026-10-08 07:50
*/
// 2128 高精度乘法(II)
// 输入两个小于 200000 位的十进制正整数 a、b,输出 a*b。
//
// 做法:把两个数看成以 10 为底的多项式,两数相乘就是多项式乘积(系数卷积),
// 用 FFT 在 O((La+Lb) log(La+Lb)) 内算出卷积,最后从低位到高位统一进位。
// 精度:单个系数最大为 min(La,Lb)*9*9 < 200000*81 ≈ 1.62e7,
// 远小于 double 尾数能精确表示的整数上限 9e15,不会有取整误差。
// 边界:输入可能出现 "0" 或前导零(如 "00000001"),按数值语义解析。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const int MAXN = 1 << 19; // 524288:不小于 (200000+200000) 的最小 2 的幂
// 手写复数:只用到加、减、乘,避免引入额外头文件依赖
struct Complex {
double r, i;
Complex() : r(0.0), i(0.0) {}
Complex(double _r, double _i) : r(_r), i(_i) {}
Complex operator+(const Complex &o) const { return Complex(r + o.r, i + o.i); }
Complex operator-(const Complex &o) const { return Complex(r - o.r, i - o.i); }
Complex operator*(const Complex &o) const {
return Complex(r * o.r - i * o.i, r * o.i + i * o.r);
}
};
Complex fa[MAXN], fb[MAXN]; // 两个多项式的系数(实部存数字,虚部为 0)
int rev[MAXN]; // 位反转置换,三次变换共用同一张表
// 迭代式 FFT:先按 rev 重排,再自底向上做蝶形合并。
// inv = 0 正变换,inv = 1 逆变换(最后除以 n)。
void fft(Complex *a, int n, int inv) {
for (int i = 0; i < n; ++i) {
if (i < rev[i]) swap(a[i], a[rev[i]]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2.0 * PI / len * (inv ? -1.0 : 1.0);
Complex wn(cos(ang), sin(ang)); // 本层的单位根
for (int i = 0; i < n; i += len) {
Complex w(1.0, 0.0);
for (int j = 0; j < len / 2; ++j) {
Complex u = a[i + j];
Complex v = a[i + j + len / 2] * w;
a[i + j] = u + v;
a[i + j + len / 2] = u - v;
w = w * wn;
}
}
}
if (inv) {
for (int i = 0; i < n; ++i) {
a[i].r /= n;
a[i].i /= n;
}
}
}
// 去掉前导零;全是零时保留一个 '0',方便统一判断零值
string stripLeadingZeros(const string &s) {
ll p = 0;
while (p + 1 < (ll)s.size() && s[p] == '0') ++p;
return s.substr(p);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string a, b;
if (!(cin >> a >> b)) return 0;
a = stripLeadingZeros(a);
b = stripLeadingZeros(b);
// 有一边为 0,乘积必为 0(题面说正整数,但数据里有 0 与前导零)
if (a == "0" || b == "0") {
printf("0\n");
return 0;
}
ll la = a.size(), lb = b.size();
int lim = 1;
while (lim < la + lb) lim <<= 1; // 不小于结果位数的 2 的幂
// 倒序填入:下标 i 对应 10^i 位
for (ll i = 0; i < la; ++i) fa[i] = Complex(a[la - 1 - i] - '0', 0.0);
for (ll i = 0; i < lb; ++i) fb[i] = Complex(b[lb - 1 - i] - '0', 0.0);
// 位反转表:rev[i] = rev[i>>1]>>1 再补上最高位
rev[0] = 0;
for (int i = 1; i < lim; ++i) {
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
}
fft(fa, lim, 0);
fft(fb, lim, 0);
for (int i = 0; i < lim; ++i) fa[i] = fa[i] * fb[i]; // 频域逐点相乘
fft(fa, lim, 1); // 逆变换回系数
// 浮点结果带微小误差,必须四舍五入而不是截断
ll carry = 0;
string out;
for (ll i = 0; i < la + lb; ++i) {
ll cur = (ll)(fa[i].r + 0.5) + carry;
out.push_back(char('0' + cur % 10));
carry = cur / 10;
}
while (carry > 0) {
out.push_back(char('0' + carry % 10));
carry /= 10;
}
while (out.size() > 1 && out.back() == '0') out.pop_back(); // 去掉高位多余零
reverse(out.begin(), out.end());
printf("%s\n", out.c_str());
return 0;
}复杂度
- 时间:一次长度为
的 FFT 是 。本题共做 3 次变换 (两次正向 + 一次逆向), 个蝶形运算;进位与输出是 。总体 , 。 实测 199999 位 × 199999 位(第 9、10 组数据)在 g++ -O2下约 60 ms,限时 1000 ms 余量充足。 - 空间:两个复数数组与
rev表,各项, 复数按 16 字节算约 8 MB,加上输出串,总峰值约 20 MB,限 128 MB 内安全。 - 与 C++ 解法的关系:Python 版不复刻 FFT,而是把乘法直接交给 CPython 的
int——它内部对超大整数用的是同阶的子二次乘法(Karatsuba 及以上), 并被sys.set_int_max_str_digits解除了十进制串转换位数上限。 这是"同阶但常数不同"的落地方式,按本题库规范允许 Python TLE; 若要在 Python 里也做到且常数可控,需要手写 FFT/NTT, 但以 CPython 的循环开销计,300 万次蝶形运算反而比 C 层大整数乘法更慢, 故短解法选择后者。
总结
- 换表示换复杂度:
是卷积,而卷积在频域就是逐点乘法; 系数表示与点值表示之间用单位复根做的变换(FFT)代价是 。 - 精度是 FFT 能用的前提:本题单个卷积和上界只有
, 远在 double精确整数范围内,这是敢用浮点 FFT 而不上 NTT 的唯一理由; 反过来,如果值域接近,就必须换 NTT。 - 进位统一在最后做:FFT 求出的是无进位的系数,先放着不进位、最后从低到高扫一遍,
既省掉了每步的同步,也避免了误差在中间步骤被放大。取整必须
round而非截断。 - 长度补到 2 的幂:迭代式 FFT 的位反转与层数都要求
是 2 的幂, 取不小于 的最小幂就够(最坏 ),比取 省一半。 - 数据是自造的:素材源含
data.py,题面为重建版,且数据里有与前导零, 实现应按数值语义解析而不是按字面的"正整数"假设。