不妨设你想插值一个 $m$ 元，次数不超过 $n$ 的多项式。可见至少需要 ${n+m\choose n}$ 项才可能解出所有项的系数。

还在想啥，弄到足够多的项解高消去啊

什么？你说 $\mathcal{O}({n+m\choose n}^{3})$ 复杂度太高了？那么 Hecht M, Cheeseman B L, Hoffmann K B, et al. A quadratic-time algorithm for general multivariate polynomial interpolation[J]. arXiv preprint arXiv:1710.10846, 2017. 提出了一个 $\mathcal{O}({n+m\choose n}^{2})$ 的算法。不过既看不懂也不想写，告辞。