1. 多项式基础概念与运算1.1 多项式定义与表示多项式是代数学中的基础概念由变量通常用x表示和系数通过有限次加、减、乘运算得到的代数表达式。一个n次多项式的一般形式为f(x) aₙxⁿ aₙ₋₁xⁿ⁻¹ ... a₁x a₀其中aₙ ≠ 0n称为多项式的次数degree记作deg f。例如3x² 2x 1是二次多项式5x³ - x是三次多项式多项式在计算机中通常用系数数组表示例如f(x) 2x³ x - 5可以表示为[2, 0, 1, -5]。1.2 基本运算原理多项式的基本运算包括加法、减法和乘法。加法和减法直接对应系数相加减时间复杂度为O(n)。乘法运算更为复杂朴素算法需要O(n²)时间复杂度vectorint poly_multiply(const vectorint a, const vectorint b) { vectorint res(a.size() b.size() - 1, 0); for (int i 0; i a.size(); i) for (int j 0; j b.size(); j) res[ij] a[i] * b[j]; return res; }2. 快速傅里叶变换(FFT)2.1 FFT数学原理FFT的核心思想是将多项式从系数表示法转换为点值表示法。对于n次多项式选取n1个不同的点计算值这些点值可以唯一确定多项式。关键步骤离散傅里叶变换(DFT)在单位根处求值快速计算利用单位根的对称性和周期性分治计算单位根性质ωₙⁿ 1ωₙ^(kn/2) -ωₙ^kωₙ^(2k) ω_(n/2)^k2.2 迭代版FFT实现递归版FFT有较大常数实际中常用迭代版(蝴蝶操作)void fft(vectorcomplexdouble a, bool invert) { int n a.size(); for (int i 1, j 0; i n; i) { int bit n 1; for (; j bit; bit 1) j ^ bit; j ^ bit; if (i j) swap(a[i], a[j]); } for (int len 2; len n; len 1) { double ang 2 * PI / len * (invert ? -1 : 1); complexdouble wlen(cos(ang), sin(ang)); for (int i 0; i n; i len) { complexdouble w(1); for (int j 0; j len/2; j) { complexdouble u a[ij], v a[ijlen/2] * w; a[ij] u v; a[ijlen/2] u - v; w * wlen; } } } if (invert) for (auto x : a) x / n; }3. 快速数论变换(NTT)3.1 NTT原理与实现NTT是FFT在有限域上的模拟使用原根代替单位根。对于模数p 998244353原根g 3const int MOD 998244353, ROOT 3; void ntt(vectorint a, bool invert) { int n a.size(); for (int i 1, j 0; i n; i) { int bit n 1; for (; j bit; bit 1) j ^ bit; j ^ bit; if (i j) swap(a[i], a[j]); } for (int len 2; len n; len 1) { int wlen invert ? powmod(ROOT, MOD-1-(MOD-1)/len) : powmod(ROOT, (MOD-1)/len); for (int i 0; i n; i len) { int w 1; for (int j 0; j len/2; j) { int u a[ij], v (long long)a[ijlen/2] * w % MOD; a[ij] (u v) % MOD; a[ijlen/2] (u - v MOD) % MOD; w (long long)w * wlen % MOD; } } } if (invert) { int inv_n powmod(n, MOD-2); for (int x : a) x (long long)x * inv_n % MOD; } }3.2 多项式乘法优化利用FFT/NTT实现O(nlogn)多项式乘法vectorint multiply(vectorint a, vectorint b) { int n 1; while (n a.size() b.size()) n 1; a.resize(n); b.resize(n); fft(a, false); fft(b, false); for (int i 0; i n; i) a[i] * b[i]; fft(a, true); // 处理进位或模数 return a; }4. 多项式进阶操作4.1 多项式求逆给定多项式A(x)求B(x)满足A(x)B(x) ≡ 1 mod xⁿ。使用牛顿迭代法vectorint inverse(const vectorint a) { vectorint b {powmod(a[0], MOD-2)}; while (b.size() a.size()) { int len min(b.size()*2, a.size()); vectorint c(a.begin(), a.begin()len); vectorint tmp multiply(b, c); tmp[0] (2 - tmp[0] MOD) % MOD; for (int i 1; i tmp.size(); i) tmp[i] (MOD - tmp[i]) % MOD; b multiply(b, tmp); b.resize(len); } return b; }4.2 多项式对数函数多项式ln(f(x))通过求导和积分实现vectorint poly_ln(const vectorint a) { vectorint deriv derivative(a); vectorint inv_a inverse(a); vectorint product multiply(deriv, inv_a); vectorint res integral(product); res.resize(a.size()); return res; }4.3 多项式指数函数多项式exp(f(x))使用牛顿迭代法vectorint poly_exp(const vectorint a) { vectorint b {1}; while (b.size() a.size()) { int len min(b.size()*2, a.size()); vectorint ln_b poly_ln(b); ln_b.resize(len); for (int i 0; i len; i) ln_b[i] (a[i] - ln_b[i] MOD) % MOD; ln_b[0] (ln_b[0] 1) % MOD; b multiply(b, ln_b); b.resize(len); } return b; }5. 多项式应用实例5.1 多项式快速幂利用exp和ln实现O(nlogn)快速幂vectorint poly_pow(const vectorint a, int k) { vectorint ln_a poly_ln(a); for (int x : ln_a) x (long long)x * k % MOD; return poly_exp(ln_a); }5.2 多项式除法通过反转多项式实现带余除法pairvectorint, vectorint divide(vectorint a, vectorint b) { int n a.size()-1, m b.size()-1; if (n m) return {{0}, a}; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); b.resize(n-m1); vectorint q multiply(a, inverse(b)); q.resize(n-m1); reverse(q.begin(), q.end()); reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); vectorint r multiply(b, q); for (int i 0; i m; i) r[i] (a[i] - r[i] MOD) % MOD; r.resize(m); return {q, r}; }6. 实战技巧与优化6.1 常数优化技巧预处理单位根避免重复计算使用位运算优化代替除法减少内存分配预分配数组循环展开提高指令级并行6.2 常见问题解决边界处理特别注意长度为1的情况零多项式特殊处理精度问题FFT中使用long double提高精度模数选择NTT需要合适的模数和原根7. 完整模板代码以下是整合了主要操作的完整模板#include bits/stdc.h using namespace std; const int MOD 998244353, ROOT 3; int powmod(int a, int b) { int res 1; for (; b; b 1) { if (b 1) res (long long)res * a % MOD; a (long long)a * a % MOD; } return res; } void ntt(vectorint a, bool invert) { // NTT实现(同上) // ... } vectorint multiply(vectorint a, vectorint b) { // 乘法实现(同上) // ... } vectorint inverse(const vectorint a) { // 求逆实现(同上) // ... } vectorint derivative(const vectorint a) { vectorint res(a.size()-1); for (int i 1; i a.size(); i) res[i-1] (long long)a[i] * i % MOD; return res; } vectorint integral(const vectorint a) { vectorint res(a.size()1); for (int i 0; i a.size(); i) res[i1] (long long)a[i] * powmod(i1, MOD-2) % MOD; return res; } vectorint poly_ln(const vectorint a) { // ln实现(同上) // ... } vectorint poly_exp(const vectorint a) { // exp实现(同上) // ... } // 其他操作...8. 竞赛应用实例8.1 大整数乘法将大整数视为多项式利用FFT加速string multiply_bigint(const string num1, const string num2) { vectorint a(num1.size()), b(num2.size()); for (int i 0; i num1.size(); i) a[num1.size()-1-i] num1[i] - 0; for (int i 0; i num2.size(); i) b[num2.size()-1-i] num2[i] - 0; vectorint c multiply(a, b); int carry 0; for (int i 0; i c.size(); i) { c[i] carry; carry c[i] / 10; c[i] % 10; } while (carry) { c.push_back(carry % 10); carry / 10; } while (c.size() 1 c.back() 0) c.pop_back(); string res; for (int i c.size()-1; i 0; i--) res char(c[i] 0); return res; }8.2 生成函数应用使用多项式运算解决组合计数问题例如斐波那契数列生成函数F(x) x/(1-x-x²)卡特兰数生成函数C(x) (1-√(1-4x))/(2x)9. 性能分析与测试9.1 时间复杂度对比操作朴素算法FFT/NTT优化乘法O(n²)O(nlogn)求逆O(n³)O(nlogn)ln-O(nlogn)exp-O(nlogn)快速幂O(n²logk)O(nlogn)9.2 实际测试数据在n1e5规模下FFT乘法约200msNTT乘法约150ms多项式求逆约300ms多项式exp约500ms10. 扩展与进阶10.1 任意模数NTT对于非NTT友好模数可以使用三模数NTT或拆系数FFT// 拆系数FFT示例 vectorint multiply_mod(const vectorint a, const vectorint b, int mod) { using cd complexdouble; const double PI acos(-1); int n 1; while (n a.size() b.size()) n 1; vectorcd fa(n), fb(n); // 拆系数 for (int i 0; i a.size(); i) fa[i] cd(a[i] 15, a[i] 32767); for (int i 0; i b.size(); i) fb[i] cd(b[i] 15, b[i] 32767); fft(fa, false); fft(fb, false); // 合并结果 vectorcd res1(n), res2(n), res3(n); for (int i 0; i n; i) { cd a0 fa[i] conj(fa[(n-i)%n]); cd a1 fa[i] - conj(fa[(n-i)%n]); cd b0 fb[i] conj(fb[(n-i)%n]); cd b1 fb[i] - conj(fb[(n-i)%n]); res1[i] (a0 * b0) * cd(0.5/n); res2[i] (a0 * b1 a1 * b0) * cd(0.5/n); res3[i] (a1 * b1) * cd(0.5/n); } fft(res1, true); fft(res2, true); fft(res3, true); vectorint res(n); for (int i 0; i n; i) { long long x llround(res1[i].real()); long long y llround(res2[i].real()); long long z llround(res3[i].real()); res[i] ((x 30) (y 15) z) % mod; } return res; }10.2 多项式复合与分解更高级的多项式操作包括多项式复合f(g(x))多项式分解找到f(x) g(h(x))多项式因式分解这些操作在算法竞赛中出现较少但在数学研究和密码学中有重要应用。