困难通用10 分钟3,440 字

多项式的表示与基本运算

多项式就像数学乐高:表示与基本运算

你有没有玩过积木?不同形状的积木可以搭出各种造型。在数学里,多项式就像一串有“重量”的积木,每个积木上标着一个数字(系数)和一个“幂次”(比如 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∑k​ai​⋅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++ 实现

cpp
#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 实现

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. 新手常见错误

  1. 数组下标混淆​​: 注意数组下标从0开始,a[i] 对应 xix^ixi。比如三次多项式 x3+2x+1x^3 + 2x + 1x3+2x+1 应该写成 [1, 2, 0, 1],而不是 [1, 0, 2, 1](把 x2x^2x2 系数也放对了)。
  2. 忘记补齐长度​​: 做加减法时,如果两个多项式长度不同,较短的数组后面缺少的项要当作0。我们的代码中用 max 取长度,然后只遍历已有索引,这是对的。如果自己写循环时忘了,可能会漏掉或访问越界。
  3. 乘法结果长度计算错误​​: 两个长度分别为 n 和 m 的多项式,乘积结果长度为 n+m-1(因为最高次是 (n-1)+(m-1))。新手容易算成 n+m 或 n+m-2,导致数组越界或丢失最高项。
  4. 打印时顺序搞反​​: 打印多项式通常从高次到低次更易读,但代码里系数存储在低次到高次。我们通过 [::-1] 或反向循环来输出。如果忘记反转,会输出成 1+2x+3x21 + 2x + 3x^21+2x+3x2 这种(虽然也是对的,但不符合习惯)。
  5. 使用浮点数系数时精度问题​​: 如果系数是小数,用 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(nlog⁡n)O(n \log n)O(nlogn),就像给积木乘法装上了火箭喷射器!接下来你可以学习:

  • FFT的原理与实现​——用点值表示法加速乘法。
  • NTT与模运算​——在整数环境下实现快速乘法,避免浮点误差。
  • 多项式高级运算​——求逆、除法、开方,甚至解方程。

继续前进,你会发现多项式世界越来越酷!

同类知识点