0%

loj#6055 题解 - 「from CommonAnts」一道数学题

题目链接加强版链接

首先你应该能推出答案 $f_k(n)$ 等于

显然有递推

你可能以为 $f_k$ 是一个 $k-1$ 次多项式,但不幸的是由于 $f_k(1)=1$ 所以它并不是……

那么学过高中数学的各位应该都知道这时候应该构造一个

也就是说

那这是好的啊,毕竟不要求 $g_k(1)=1$,它可以是一个 $k-1$ 次多项式啊

那么 $g_k(n)$ 盲猜一下必然要拉格朗日插值,我们求 $k$ 个点值就好了,而从一个点值就可以递推出所有的点值,所以我们只需要求 $g_k(0)$ 就好了

考虑所有其他点值都可以被 $kg_k(0)+b$ 表示,那么我们再掏出一个方程就可以解出 $g_k(0)$ 了

这里有一个恒等式

把 $g^k(i)$ 看成 $\text{E}^ig^k(0)$,那么等式左边其实就是 $\Delta^kg_k(0)$,而 $g_k$ 是一个 $k-1$ 次多项式,差分 $k$ 次当然是 0,也就证明了上面的式子

于是大力插值即可。