Nvidia C 语言多项式乘法：系数卷积与 API 边界

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 系数数组按幂次升序，a[i] 表示 x^i 的系数；允许中间幂次系数为 0。输入长度均至少为 1。
• 调用者提供长度至少 na+nb−1 的输出缓冲区，且输出与输入存储不重叠；系数乘积与累加保证落在 int64_t 范围内。
• 返回 0 成功、−1 表示空指针/长度溢出等无效输入、−2 表示输出空间不足；这些错误码是训练接口约定，不是题目规定。

解题路线

1. 先推导结果最高次数为 (na−1)+(nb−1)，所以输出长度为 na+nb−1；在 C 中先检查长度计算和字节数不会溢出。
2. 把输出所需区间清零，对每个输入系数 a[i] 与 b[j]，把乘积累加到 out[i+j]。这是多项式卷积的直接实现。
3. 用 C API 显式传入指针、长度和输出容量，避免函数内部隐藏分配所有权；调用者可用返回码判断错误。
4. 在测试中按相同升序约定手算例子，再用另一份 Python 卷积做小数组随机对照。

手动走一遍

a=[5,−2,0,1]、b=[4,2,1] 分别表示 x³−2x+5 和 x²+2x+4。常数项 5×4=20，x 项 5×2+(−2)×4=2，最终结果升序为 [20,2,1,2,2,1]，对应 x⁵+2x⁴+2x³+x²+2x+20。

C 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

#include <stddef.h>
#include <stdint.h>
#include <string.h>

/* Coefficients are in ascending power order: a[i] is the coefficient of x^i.
   Returns 0 on success, -1 for invalid input, -2 for insufficient output space.
   Caller supplies output storage; coefficient arithmetic must fit int64_t. */
int multiply_polynomials(const int64_t *a, size_t na,
                         const int64_t *b, size_t nb,
                         int64_t *out, size_t out_capacity) {
    if (a == NULL || b == NULL || out == NULL || na == 0 || nb == 0 ||
        na > SIZE_MAX - nb + 1) {
        return -1;
    }
    size_t required = na + nb - 1;
    if (required > SIZE_MAX / sizeof(int64_t)) {
        return -1;
    }
    if (out_capacity < required) {
        return -2;
    }
    memset(out, 0, required * sizeof(int64_t));
    for (size_t i = 0; i < na; ++i) {
        for (size_t j = 0; j < nb; ++j) {
            out[i + j] += a[i] * b[j];
        }
    }
    return 0;
}

复杂度

na×nb 对系数相乘，时间 O(na·nb)，除调用者提供的结果数组外额外空间 O(1)，输出必须有 O(na+nb) 个系数。若输入极长且稠密，FFT 可降低渐近时间，但会改变实现复杂度与数值误差，需要先确认约束。

易错点与追问

容易失分的边界

• 把数组按降幂解析，却按升幂写输出，示例会看似接近但完全错误。
• 没有检查输出容量，C 代码可能越界写入；没有检查 na+nb−1 溢出，容量判断也会失效。
• 输出与输入指针重叠时清零会破坏输入；训练接口要求不重叠，若必须支持原地运算需使用临时缓冲区。
• int64_t 中间乘积或累加可能溢出；题目没有数值范围，面试时应先问清并选择检查或更宽整数。

继续深挖

• 稀疏多项式可只遍历非零项，结果按幂次合并；要比较稀疏度阈值和数据结构开销。
• 若要函数分配输出，返回结构体时同时给长度和明确的 free 责任。
• 若要求系数可能溢出，使用 checked arithmetic 返回错误码，而不是在 C 中依赖有符号溢出行为。