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

GKxx

2019-02-03 15:53:56

Solution

本蒟蒻第一次做这种亦可赛艇的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)$,另外就算横坐标不是连续的整数我们也可以用一些玄妙的做法[快速插值](https://www.luogu.org/problemnew/show/P5158)。但是本题$n\leq500$,就随意啦 代码比较简单,就不贴了。