题解 P4463 【[国家集训队] calc】

· · 题解

本蒟蒻第一次做这种亦可赛艇的DP优化...

真是妙不可言啊

首先我们有一个暴力的DP：f(i,j)表示前i个数取值域范围[1,j]的所有不同合法序列的值之和。但是这样转移并不方便。我们可以只考虑递增的序列，考虑第i个数取不取j，于是有转移

f(i,j)=f(i-1,j-1)\times j+f(i,j-1)

最后对于每个递增序列都可以任意重排，所以答案是f(n,A)\times n!。

这样做的复杂度是O(nA)的，并不能通过，需要优化。

首先你要知道一个定理：平面上横坐标不同的任意n+1个点可以唯一确定一个次数不高于n的多项式p(x)，可以使用拉格朗日插值公式来确定：

p(x)=\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}\frac{x-x_j}{x_i-x_j}

假设f(n,i)是关于i的g(n)次多项式，我们来推导g(n)的表达式。

注意到：如果p(x)是n次多项式，那么差分p(x)-p(x-1)是n-1次多项式。证明比较显然。

然后我们发现f(n,i)的转移方程里有差分的形式：

f(n,i)-f(n,i-1)=f(n-1,i-1)\times i

观察这个式子。左边是关于i的g(n)-1次多项式，右边是关于i的g(n-1)+1次多项式，于是我们有

g(n)-1=g(n-1)+1

当n=0时显然有

g(0)=0

不难发现g(n)是等差数列，得到g(n)=2n

利用数学归纳法直接按照转移方程归纳也可以证明，但我这里是在未知结论的情况下正面推导的。

既然f(n,i)是关于i的2n次多项式，我们就不需要求出f(n,A)，只要求出f(n,1)到f(n,2n+1)，就有了2n+1个点，利用拉格朗日插值即可插出f(n,A)的值。

直接利用拉格朗日插值公式是O(n^2)的，当横坐标是连续的整数的时候可以预处理前缀积和后缀积来优化到O(n)，另外就算横坐标不是连续的整数我们也可以用一些玄妙的做法快速插值。但是本题n\leq500，就随意啦

代码比较简单，就不贴了。