自动搬运

查看原文

来自洛谷，原作者为

	GKxx 欲买桂花同载酒，终不似，少年游。

搬运于2025-08-24 22:00:27，当前版本为作者最后更新于2019-02-03 15:53:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

本蒟蒻第一次做这种亦可赛艇的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$，就随意啦

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