多项式乘法 c++数据结构

多项式乘法可以使用多种数据结构实现，其中较常见的是数组和链表。

1. 数组实现

假设要计算两个多项式 $A(x)$ 和 $B(x)$ 的乘积，它们的系数分别为 $a_0, a_1, \cdots, a_n$ 和 $b_0, b_1, \cdots, b_m$，则它们的乘积的系数为 $c_0, c_1, \cdots, c_{n+m}$，其中 $c_k = \sum\limits_{i+j=k} a_i b_j$。代码如下：

const int N = 1e5 + 5;

int a[N], b[N], c[N];

void multiply(int n, int m) {
    for (int i = 0; i <= n + m; ++i) {
        c[i] = 0;
        for (int j = 0; j <= i; ++j) {
            c[i] += a[j] * b[i - j];
        }
    }
}

2. 链表实现

链表实现的思路与数组实现类似，只不过是用链表存储多项式的系数。具体来说，我们可以用一个结构体来存储每一项的系数和指数，然后把这些结构体按照指数从小到大排序。代码如下：

struct Term {
    int coef, exp;
    Term *next;
};

Term *headA, *headB, *headC;

void multiply() {
    for (Term *p = headA; p != nullptr; p = p->next) {
        for (Term *q = headB; q != nullptr; q = q->next) {
            int coef = p->coef * q->coef;
            int exp = p->exp + q->exp;
            Term *r = headC;
            while (r->next != nullptr && r->next->exp > exp) {
                r = r->next;
            }
            if (r->next != nullptr && r->next->exp == exp) {
                r->next->coef += coef;
            } else {
                Term *s = new Term{coef, exp, r->next};
                r->next = s;
            }
        }
    }
}

以上两种实现方式都可以在 $O(nm)$ 的时间复杂度内完成多项式乘法。但是，当多项式的次数较高时，数组实现可能会因为数组过大而导致空间不足，而链表实现则没有这个问题。