CC++ & Algorithm

多项式的表示与基本运算

困难2
语言版本：通用
概述：多项式就像一串带着系数的积木，加减法像搭积木，乘法像积木的卷积，我们把它们的数学原理和代码实现讲清楚。

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

你有没有玩过积木？不同形状的积木可以搭出各种造型。在数学里，多项式就像一串有“重量”的积木，每个积木上标着一个数字（系数）和一个“幂次”（比如 x2x^2、xx）。把多项式加起来，就像把积木按形状堆在一起；乘起来，就像把两种积木组合成新的积木——这个过程叫做卷积。学会多项式的基本运算，你就能轻松处理很多数学和编程问题，比如做大数乘法、处理信号、做图像压缩，甚至还可以解方程呢！

1. 什么是多项式？——积木的两种摆法

系数表示法：就像把所有积木按幂次从低到高排成一排。比如多项式

A(x)=3x2+2x+1A(x) = 3x^2 + 2x + 1

可以写成系数列表：[1, 2, 3]。

  • 第一个数字 1 是常数项（x0x^0 的系数），
  • 第二个 2 是 xx 的系数，
  • 第三个 3 是 x2x^2 的系数。

注意：下标从0开始，a[i] 就是 xix^i 的系数。如果多项式有缺项，比如 2x+52x + 5，我们就写成 [5, 2]，把 x2x^2 的系数当作0。这种表示法最常用，计算机存起来很方便。

点值表示法：换一种玩法——找几个不同的 xx，把多项式代进去算一算，得到几个点 (xi,yi)(x_i, y_i)。比如对于上面的二次多项式，我们可以选 x=0,1,2x = 0, 1, 2：

  • 当 x=0x=0，y=1y = 1 → 点 (0,1)
  • 当 x=1x=1，y=3+2+1=6y = 3+2+1 = 6 → 点 (1,6)
  • 当 x=2x=2，y=12+4+1=17y = 12+4+1 = 17 → 点 (2,17)

如果我们选取的点数比多项式的次数多1（这里是3个），那么这些点就能唯一确定这个多项式。点值表示法在后面的FFT（快速傅里叶变换）中特别有用，因为它能让我们快速做乘法。

2. 多项式的加减法——像算零花钱一样简单

假设你每天有零花钱，今天妈妈给你 A(x)=3x2+2x+1A(x) = 3x^2 + 2x + 1 元（这只是一个比喻，x只是个符号），爸爸给你 B(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 + 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 - 4

注意：次数不同的多项式，我们只需要把缺少的幂次系数当成0。比如 A 有 x2x^2，B 没有，那就相当于 B 的 x2x^2 系数是0。

生活小例子：

  • 加法：把两盒积木混在一起，红色积木和蓝色积木各自归类。
  • 减法：从一盒积木里拿走另一盒积木里相同颜色的积木。

3. 多项式的乘法（卷积）——组合零食的神奇算法

乘法比加减法有趣得多！两个多项式相乘，结果的系数是原来系数的卷积。举个例子：

A(x)=1+2x+3x2,B(x)=5+4xA(x) = 1 + 2x + 3x^2, \quad B(x) = 5 + 4x

让我们像小学乘法一样，一项一项乘：

  • 1×(5+4x)=5+4x1 \times (5 + 4x) = 5 + 4x
  • 2x×(5+4x)=10x+8x22x \times (5 + 4x) = 10x + 8x^2
  • 3x2×(5+4x)=15x2+12x33x^2 \times (5 + 4x) = 15x^2 + 12x^3

然后合并相同幂次的系数：

  • 常数项：5（只有第一个）
  • xx 项：4 + 10 = 14
  • x2x^2 项：8 + 15 = 23
  • x3x^3 项：12

所以结果 C(x)=5+14x+23x2+12x3C(x) = 5 + 14x + 23x^2 + 12x^3，系数列表是 [5, 14, 23, 12]。

一般公式：如果 AA 有 nn 项（最高次 n−1n-1），BB 有 mm 项（最高次 m−1m-1），那么乘积有 n+m−1n+m-1 项，第 kk 项系数是：

ck=∑i=0kai⋅bk−ic_k = \sum_{i=0}^{k} a_i \cdot b_{k-i}

其中 aia_i 和 bk−ib_{k-i} 如果超出范围就当作0。这个运算叫做卷积，它的思想和“组合零食”很像：

  • 你有两种零食包：一种有苹果味（aia_i），一种有香蕉味（bjb_j）。
  • 把两包混合，每种新口味（ckc_k）是苹果和香蕉所有可能组合的总和，只要它们的“口味编号”加起来等于 kk。

生活中的卷积：比如你买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. 新手常见错误

  1. 数组下标混淆：
    注意数组下标从0开始，a[i] 对应 xix^i。比如三次多项式 x3+2x+1x^3 + 2x + 1 应该写成 [1, 2, 0, 1]，而不是 [1, 0, 2, 1]（把 x2x^2 系数也放对了）。

  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^2 这种（虽然也是对的，但不符合习惯）。

  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(nlog⁡n)O(n \log n)，就像给积木乘法装上了火箭喷射器！接下来你可以学习：

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

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

例题精讲

1单选题

对于两个次数均为 n 的多项式 A(x) 和 B(x)，如果使用直接系数乘法（暴力卷积）计算它们的乘积，时间复杂度是多少？如果使用快速傅里叶变换（FFT），时间复杂度是多少？

AO(n^2) 和 O(n)
BO(n^2) 和 O(n log n)
CO(n^3) 和 O(n log n)
DO(n^2) 和 O(n^2)
2判断题

两个次数相同但项数不全的多项式相加时，只需将对应次数的系数相加即可，次数不同的项直接保留。

3填空题
以下函数实现两个多项式的加法，多项式用数组表示，下标 i 对应 x^i 的系数，数组长度最大为 MAXN。请补全代码。

void poly_add(int A[], int B[], int C[], int n) {
    // 将 A 和 B 的系数加到 C，n 为最高次数
    for (int i = 0; i <= n; i++) {
        C[i] = ___(1)___;
    }
}
4单选题

在快速傅里叶变换（FFT）中，多项式通常先转换成点值表示再进行乘法。为什么点值表示下乘法更容易？

A因为点值表示下乘法变成了点对点的乘法，复杂度 O(n)
B因为点值表示下系数都是实数，计算更简单
C因为点值表示不需要存储所有系数
D因为点值表示可以直接得到乘积多项式的系数表示
5填空题
下面代码用暴力方法计算两个多项式的乘积，数组 A 和 B 的系数存储从 0 到 n 次。请补全双重循环。

void poly_mul_brute(int A[], int B[], int C[], int n) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            ___(1)___ += A[i] * B[j];
        }
    }
}