多项式的表示与基本运算
多项式就像数学乐高:表示与基本运算
你有没有玩过积木?不同形状的积木可以搭出各种造型。在数学里,多项式就像一串有“重量”的积木,每个积木上标着一个数字(系数)和一个“幂次”(比如 x2x^2x2、xxx)。把多项式加起来,就像把积木按形状堆在一起;乘起来,就像把两种积木组合成新的积木——这个过程叫做卷积。学会多项式的基本运算,你就能轻松处理很多数学和编程问题,比如做大数乘法、处理信号、做图像压缩,甚至还可以解方程呢!
1. 什么是多项式?——积木的两种摆法
系数表示法:就像把所有积木按幂次从低到高排成一排。比如多项式
A(x)=3x2+2x+1A(x) = 3x^2 + 2x + 1A(x)=3x2+2x+1
可以写成系数列表:[1, 2, 3]。
- 第一个数字
1是常数项(x0x^0x0 的系数), - 第二个
2是 xxx 的系数, - 第三个
3是 x2x^2x2 的系数。
注意:下标从0开始,a[i] 就是 xix^ixi 的系数。如果多项式有缺项,比如 2x+52x + 52x+5,我们就写成 [5, 2],把 x2x^2x2 的系数当作0。这种表示法最常用,计算机存起来很方便。
点值表示法:换一种玩法——找几个不同的 xxx,把多项式代进去算一算,得到几个点 (xi,yi)(x_i, y_i)(xi,yi)。比如对于上面的二次多项式,我们可以选 x=0,1,2x = 0, 1, 2x=0,1,2:
- 当 x=0x=0x=0,y=1y = 1y=1 → 点 (0,1)
- 当 x=1x=1x=1,y=3+2+1=6y = 3+2+1 = 6y=3+2+1=6 → 点 (1,6)
- 当 x=2x=2x=2,y=12+4+1=17y = 12+4+1 = 17y=12+4+1=17 → 点 (2,17)
如果我们选取的点数比多项式的次数多1(这里是3个),那么这些点就能唯一确定这个多项式。点值表示法在后面的FFT(快速傅里叶变换)中特别有用,因为它能让我们快速做乘法。
2. 多项式的加减法——像算零花钱一样简单
假设你每天有零花钱,今天妈妈给你 A(x)=3x2+2x+1A(x) = 3x^2 + 2x + 1A(x)=3x2+2x+1 元(这只是一个比喻,x只是个符号),爸爸给你 B(x)=4x+5B(x) = 4x + 5B(x)=4x+5 元。要算你一共有多少钱,就把相同幂次的系数加起来:
A(x)+B(x)=(3+0)x2+(2+4)x+(1+5)=3x2+6x+6A(x) + B(x) = (3+0)x^2 + (2+4)x + (1+5) = 3x^2 + 6x + 6A(x)+B(x)=(3+0)x2+(2+4)x+(1+5)=3x2+6x+6
如果爸爸又想把他的零花钱拿回去,那就是减法:
A(x)−B(x)=(3−0)x2+(2−4)x+(1−5)=3x2−2x−4A(x) - B(x) = (3-0)x^2 + (2-4)x + (1-5) = 3x^2 - 2x - 4A(x)−B(x)=(3−0)x2+(2−4)x+(1−5)=3x2−2x−4
注意:次数不同的多项式,我们只需要把缺少的幂次系数当成0。比如 A 有 x2x^2x2,B 没有,那就相当于 B 的 x2x^2x2 系数是0。
生活小例子:
- 加法:把两盒积木混在一起,红色积木和蓝色积木各自归类。
- 减法:从一盒积木里拿走另一盒积木里相同颜色的积木。
3. 多项式的乘法(卷积)——组合零食的神奇算法
乘法比加减法有趣得多!两个多项式相乘,结果的系数是原来系数的卷积。举个例子:
A(x)=1+2x+3x2,B(x)=5+4xA(x) = 1 + 2x + 3x^2, \quad B(x) = 5 + 4xA(x)=1+2x+3x2,B(x)=5+4x
让我们像小学乘法一样,一项一项乘:
- 1×(5+4x)=5+4x1 \times (5 + 4x) = 5 + 4x1×(5+4x)=5+4x
- 2x×(5+4x)=10x+8x22x \times (5 + 4x) = 10x + 8x^22x×(5+4x)=10x+8x2
- 3x2×(5+4x)=15x2+12x33x^2 \times (5 + 4x) = 15x^2 + 12x^33x2×(5+4x)=15x2+12x3
然后合并相同幂次的系数:
- 常数项:
5(只有第一个) - xxx 项:
4 + 10 = 14 - x2x^2x2 项:
8 + 15 = 23 - x3x^3x3 项:
12
所以结果 C(x)=5+14x+23x2+12x3C(x) = 5 + 14x + 23x^2 + 12x^3C(x)=5+14x+23x2+12x3,系数列表是 [5, 14, 23, 12]。
一般公式:如果 AAA 有 nnn 项(最高次 n−1n-1n−1),BBB 有 mmm 项(最高次 m−1m-1m−1),那么乘积有 n+m−1n+m-1n+m−1 项,第 kkk 项系数是:
ck=∑i=0kai⋅bk−ic_k = \sum_{i=0}^{k} a_i \cdot b_{k-i}ck=i=0∑kai⋅bk−i
其中 aia_iai 和 bk−ib_{k-i}bk−i 如果超出范围就当作0。这个运算叫做卷积,它的思想和“组合零食”很像:
- 你有两种零食包:一种有苹果味(aia_iai),一种有香蕉味(bjb_jbj)。
- 把两包混合,每种新口味(ckc_kck)是苹果和香蕉所有可能组合的总和,只要它们的“口味编号”加起来等于 kkk。
生活中的卷积:比如你买2元一支的笔和3元一块的橡皮,总共10元能买几种组合?这其实就是在解一个多项式乘法问题。
4. 编程实现——用数组做积木计算
在C++或Python中,我们用数组(或列表)来存多项式的系数,下标就是幂次。下面给出完整代码,每行都有中文注释,方便理解。
C++ 实现
#include <iostream>
#include <vector>
using namespace std;
// 打印多项式(从高次到低次,便于阅读)
void printPoly(const vector<int>& poly) {
bool first = true; // 是否是第一个非零项
for (int i = poly.size() - 1; i >= 0; --i) { // 从最高次开始
if (poly[i] == 0) continue; // 跳过系数为0的项
if (!first) cout << " + "; // 不是第一项时加加号
first = false;
if (i == 0) cout << poly[i]; // 常数项
else if (i == 1) cout << poly[i] << "x"; // 一次项
else cout << poly[i] << "x^" << i; // 高次项
}
if (first) cout << "0"; // 全是0时输出0
cout << endl;
}
// 多项式加法:返回两个多项式的和
vector<int> addPolynomials(const vector<int>& a, const vector<int>& b) {
int n = max(a.size(), b.size()); // 结果多项式的长度(最高次数+1)
vector<int> result(n, 0); // 初始化结果数组,所有元素为0
for (int i = 0; i < a.size(); ++i) result[i] += a[i]; // 加上A的系数
for (int i = 0; i < b.size(); ++i) result[i] += b[i]; // 加上B的系数
return result;
}
// 多项式减法:返回 a - b
vector<int> subtractPolynomials(const vector<int>& a, const vector<int>& b) {
int n = max(a.size(), b.size());
vector<int> result(n, 0);
for (int i = 0; i < a.size(); ++i) result[i] += a[i];
for (int i = 0; i < b.size(); ++i) result[i] -= b[i];
return result;
}
// 多项式乘法(暴力卷积):返回 a * b
// 时间复杂度 O(n*m),n和m分别是两个多项式的长度
vector<int> multiplyPolynomials(const vector<int>& a, const vector<int>& b) {
int n = a.size(); // A 的次数+1
int m = b.size(); // B 的次数+1
// 乘积的最高次数为 (n-1)+(m-1) = n+m-2,所以数组长度是 n+m-1
vector<int> result(n + m - 1, 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
result[i + j] += a[i] * b[j]; // 对应项相乘,加到对应幂次上
}
}
return result;
}
int main() {
// 示例:A(x) = 3x^2 + 2x + 1 => 系数 [1, 2, 3]
vector<int> A = {1, 2, 3};
// B(x) = 4x + 5 => 系数 [5, 4]
vector<int> B = {5, 4};
cout << "多项式 A: ";
printPoly(A);
cout << "多项式 B: ";
printPoly(B);
vector<int> sum = addPolynomials(A, B);
cout << "A + B = ";
printPoly(sum);
vector<int> diff = subtractPolynomials(A, B);
cout << "A - B = ";
printPoly(diff);
vector<int> prod = multiplyPolynomials(A, B);
cout << "A * B = ";
printPoly(prod);
return 0;
}
Python 实现
def print_poly(poly):
"""打印多项式,从高次到低次"""
terms = [] # 存放每个打印项(字符串)
for i, coeff in enumerate(poly):
if coeff == 0:
continue
if i == 0:
terms.append(str(coeff)) # 常数项
elif i == 1:
terms.append(f"{coeff}x") # 一次项
else:
terms.append(f"{coeff}x^{i}") # 高次项
if not terms:
print("0")
else:
# 反转列表使高次在前,用" + "连接
print(" + ".join(terms[::-1]))
def add_polynomials(a, b):
"""多项式加法"""
n = max(len(a), len(b))
result = [0] * n # 初始化结果列表
for i in range(len(a)):
result[i] += a[i]
for i in range(len(b)):
result[i] += b[i]
return result
def subtract_polynomials(a, b):
"""多项式减法:a - b"""
n = max(len(a), len(b))
result = [0] * n
for i in range(len(a)):
result[i] += a[i]
for i in range(len(b)):
result[i] -= b[i]
return result
def multiply_polynomials(a, b):
"""多项式乘法(暴力卷积)"""
n = len(a)
m = len(b)
result = [0] * (n + m - 1) # 乘积数组长度
for i in range(n):
for j in range(m):
result[i + j] += a[i] * b[j]
return result
# 测试
A = [1, 2, 3] # A(x) = 3x^2 + 2x + 1
B = [5, 4] # B(x) = 4x + 5
print("多项式 A: ", end="")
print_poly(A)
print("多项式 B: ", end="")
print_poly(B)
sum_poly = add_polynomials(A, B)
print("A + B = ", end="")
print_poly(sum_poly)
diff_poly = subtract_polynomials(A, B)
print("A - B = ", end="")
print_poly(diff_poly)
prod_poly = multiply_polynomials(A, B)
print("A * B = ", end="")
print_poly(prod_poly)
5. 新手常见错误
- 数组下标混淆: 注意数组下标从0开始,
a[i]对应 xix^ixi。比如三次多项式 x3+2x+1x^3 + 2x + 1x3+2x+1 应该写成[1, 2, 0, 1],而不是[1, 0, 2, 1](把 x2x^2x2 系数也放对了)。 - 忘记补齐长度: 做加减法时,如果两个多项式长度不同,较短的数组后面缺少的项要当作0。我们的代码中用
max取长度,然后只遍历已有索引,这是对的。如果自己写循环时忘了,可能会漏掉或访问越界。 - 乘法结果长度计算错误: 两个长度分别为 n 和 m 的多项式,乘积结果长度为 n+m-1(因为最高次是 (n-1)+(m-1))。新手容易算成 n+m 或 n+m-2,导致数组越界或丢失最高项。
- 打印时顺序搞反: 打印多项式通常从高次到低次更易读,但代码里系数存储在低次到高次。我们通过
[::-1]或反向循环来输出。如果忘记反转,会输出成 1+2x+3x21 + 2x + 3x^21+2x+3x2 这种(虽然也是对的,但不符合习惯)。 - 使用浮点数系数时精度问题: 如果系数是小数,用
double或float时可能出现 0.1+0.2 ≠ 0.3 的浮点误差。在竞赛中常用整数或取模运算。
6. 完整示例运行结果
运行上面的C++或Python代码,你会看到:
多项式 A: 3x^2 + 2x + 1
多项式 B: 4x + 5
A + B = 3x^2 + 6x + 6
A - B = 3x^2 - 2x - 4
A * B = 12x^3 + 23x^2 + 14x + 5
和你手算的结果完全一样!你可以修改 A 和 B 的系数,试试其他多项式。
7. 相关指引
现在你已经学会了多项式的基本运算,但暴力乘法的速度太慢了(比如两个1000次的多项式相乘,需要100万次运算,在计算机里勉强能接受,但如果次数更大,比如10万次,就慢得像蜗牛)。别担心,我们有更快的算法:FFT(快速傅里叶变换) 和 NTT(快速数论变换),它们能把乘法从 O(nm)O(nm)O(nm) 降到 O(nlogn)O(n \log n)O(nlogn),就像给积木乘法装上了火箭喷射器!接下来你可以学习:
- FFT的原理与实现——用点值表示法加速乘法。
- NTT与模运算——在整数环境下实现快速乘法,避免浮点误差。
- 多项式高级运算——求逆、除法、开方,甚至解方程。
继续前进,你会发现多项式世界越来越酷!