稠密多项式表示

稠密表示像一把从 $0$ 次刻到 $d$ 次的直尺：即使某个刻度上的系数为零，该位置仍然保留。因此“第 $i$ 项在哪里”无需搜索，卷积、Horner 求值、求形式导数和长除法都能沿连续内存规则前进。算法分析中常写的 $M(n)$，也正是以长度约为 $n$ 的这类系数向量为基本输入，计算两个次数小于 $n$ 的多项式乘积所需的环运算数。

连续位置还使分治切块十分自然。把长度 $2m$ 的向量分成低半与高半，就得到

Karatsuba、Toom–Cook 与基于变换的乘法都利用这一分解。不过“数组连续”只描述布局，不自动保证快速：若运算会产生巨大的整数系数，真正瓶颈可能是单个系数的乘法和内存分配，而不是数组下标。

多项式

的规范稠密编码是 $(5,0,0,-2,0,0,7)$。与 $g(x)=1+x$ 相乘时，先把原向量复制到结果的相邻两段并相加：

所以结果数组为 $(5,5,0,-2,-2,0,7,7)$。这个计算展示了卷积中每个 $a_i$ 同时贡献到 $c_i$ 与 $c_{i+1}$，也说明内部零项并不会破坏统一循环。

规范化不可省略。向量 $(2,3,0,0)$ 与 $(2,3)$ 表示同一形式多项式；若不删除尾随零，次数测试、除法终止条件与相等判断都会产生分歧。系数环有零因子时，乘积的最高项还可能消失，例如在 $(\mathbb{Z}/4\mathbb{Z})[x]$ 中 $(2x)(2x)=0$，因此不能无条件预分配为“次数恰好相加”后就跳过末尾归一化。

当 $f=1+x^{{10}^9}$ 时，稠密表示需要十亿零位，问题规模显然不应再按次数衡量；这正是稀疏多项式表示理路稀疏多项式表示Sparse polynomial representation · Term-list polynomial representation只保存非零系数及其指数、以项数而非最高次数计量规模的多项式编码。胜出的边界。反过来，一个看似稀疏的输入经过乘法后可能填满几乎所有次数，此时持续维护项表和哈希表反而比连续向量昂贵。表示选择必须依据非零项数、次数跨度与运算后的密度，而不是只看输入文件是否短。

稠密编码为多项式乘法理路多项式乘法算法Polynomial multiplication algorithm · Fast polynomial multiplication以卷积、分治或点值变换计算系数乘积，并以乘法代价函数统一后续多项式算法。提供统一的 $M(n)$ 接口，也适合乘积树、快速多点求值以及多项式余式序列。它使“截断到模 $x^k$”“反转前 $k$ 项”“取低半系数”都成为明确的数组切片操作，从而把 Newton 反演和快速除法写成可实现的递推，而不只是形式恒等式。

在工程实现中还要区分逻辑长度与容量。频繁相乘若每次都按精确长度重新分配，会把线性搬运成本叠加到代数运算上；保留容量可以减少分配，但逻辑末尾仍须归一化。若系数是模素数机器字，可用平坦数组获得良好局部性；若系数是大整数，数组只保存对象引用时，空间估计还必须加入每个系数的独立存储。由此可见，稠密表示不是“多项式的唯一自然形态”，而是一套让次数范围成为主要规模参数的具体成本模型。