已知 $n$ 次多项式 $P(x)$ 在 $n+1$ 个点的值 $P(x_0),P(x_1),\cdots,P(x_n)$，则
$$
P(x)=\sum_{i=0}^nP(x_i)\prod_{0\leq j\leq n,j\neq i}\frac{x-x_j}{x_i-x_j}
$$
正确性不难证明：
$$
P(x_k)=\sum_{i=0}^nP(x_i)\prod_{0\leq j\leq n,j\neq i}\frac{x_k-x_j}{x_i-x_j}
$$
当 $i\neq k$ 时，存在一个 $j\neq i$ 满足 $j=k$ 从而使后面的值为 $0$；当 $i=k$ 时，后面的值为 $1$。所以等号右边为 $P(x_k)$，正确性得证。

考虑一种特殊情况，即 $x_0=0,x_1=1,\cdots,x_n=n$ 时
$$
P(x)=\sum_{i=0}^nP(i)\prod_{0\leq j\leq n,j\neq i}\frac{x-j}{i-j}
$$
先计算 $\prod_{0\leq j\leq n,j\neq i}(x-j)$。显然它等于
$$
\frac{x(x-1)\cdots(x-n)}{x-i}
$$
再考虑计算 $\prod_{0\leq j\leq n,j\neq i}\frac{1}{i-j}$。
$$
\begin{aligned}
&\prod_{0\leq j\leq n,j\neq i}\frac{1}{i-j}\\
=&\prod_{j=0}^{i-1}\frac{1}{i-j}\prod_{j=i+1}^n\frac{1}{i-j}\\
=&\frac{1}{i!}\times(-1)^{n-i}\frac{1}{(n-i)!}
\end{aligned}
$$
所以
$$
P(x)=\sum_{i=0}^n(-1)^{n-i}P(i)\frac{x(x-1)\cdots(x-n)}{(x-i)i!(n-i)!}
$$