自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:14:01，当前版本为作者最后更新于2025-04-20 20:47:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

来个拉格朗日插值优化 DP 的方法。现在的安徽小朋友越来越不容易了，一年一年的上强度。

阅读题面的时候一眼看到三个可：，非常有趣。

可能会有一些小朋友阅读这篇文章，所以我写的详细一些。

首先，考虑固定局面下小可可怎么取牌可以获得最大收益。

假设有一个集合 $U=\{1,2,3,\cdots,2n\}$ 表示牌的编号（注意和牌上的值并不相通），小可可选取的牌的集合 $C$ 是 $U$ 的一个大小为 $n$ 的子集。在这 $\binom{2n}{n}$ 个子集中，我们需要选出合法的且代价最大的那一个。

为什么要强调“合法”呢？比如，小可可并不能选出前 $n$ 张牌（$n \ge 2$），因为波特肯定会在第一张牌和第二张牌中选出一个。

我们断言：小可可取出的集合 $C$ 合法，当且仅当 $\forall 1 \le k \le n$，$C$ 中小于等于 $2k$ 的牌的个数 $\le k$。使用数学归纳法容易证明。

那么不妨设小可可初始的牌放在 $1$，$3$，$\cdots$，$2n-1$。每一张牌可以移动到后面的任何一个位置，最终不能重叠。换句话说，小可可的最后一张牌可以在后两张牌中选取，倒数第二张排可以在后四张牌中选取，依次类推。

这样我们就会计算答案了——显然每一步都可以贪心。所以你开一个堆，从 $n$ 到 $1$，每次往堆里面加入 $2$ 个 $a_i$，并且取出堆顶。复杂度 $O(m^n \times n \log n)$。

这样也许可以拿到 $24$ 分？看你常数怎么样了。拿到这档分的小朋友未来很有希望的：你有很强的分析问题的能力，和获得更高的分只差了经典技巧的积累，多做点题就能克服这一关了！

这类问题有一个经典的讨论：“二分”转 $01$。

设 $f_i$ 表示，最终取出的 $n$ 张牌中，有多少张排的大小 $\ge i$。答案显然就是 $\sum_{i=1}^m f_i$。根据期望的线性性，$E(\sum_{i=1}^m f_i) = \sum_{i=1}^m E(f_i)$，所以你想方设法算出 $E(f_i)$。

可以证明，$f_i$ 等于：将 $\ge i$ 的数看做 $1$，$\le i$ 的数看做 $0$，执行上面贪心的流程得到的结果。

这么做的好处是什么呢？由于所有数要么是 $0$ 要么是 $1$，我们只需要关心堆里面有多少个 $1$，而这样的状态数就比较少，可以进行 DP！（这里有点 DP 套 DP 的感觉了，和去年 T4 很像！）

假设我们需要求 $f_x$。设 $dp_{i,j}$ 表示，执行了所有 $i_0 \ge i$ 后，堆中有 $j$ 个 $1$ 的概率。最终状态是 $dp_{1,j}$，表示堆里面还剩了 $j$ 个 $1$。这样假设加入了 $k$ 个 $1$，小可可就取出了 $k-j$ 个 $1$。我们的答案是 $E(k-j)=E(k)-E(j)$，其中 $E(j) = \sum_j (j-\min\{j,i-1\}) dp_{i,j}$，$E(k) = E(\sum_{i=1}^n [a_i \ge x]) = \sum_{i=1}^n E([a_i \ge x]) = \sum_{i=1}^n p(a_i \ge x)$，其中 $p$ 表示概率。

$dp_{i,j}$ 的转移是容易的，你分类讨论一下 $a_i$ 和 $x$ 的关系即可。

复杂度 $O(n^2 m)$，可以拿到 $52$ 分。拿到这一档分的小朋友很强大：你有很强的算法功底，和正解只差了高级算法，多学一段时间就可以克服！

给定 $x$ 做 DP 的时候，$[a_i \ge x]$ 一共有 $2^n$ 种可能。每一种可能都有出现的概率 $p(A)$，以及贡献 $c(A)$。$c(A)$ 在 $A$ 确定的时候是一个常数，而 $p(A)$ 应当是每一位对应概率的乘积。而这个概率要么是常数，要么是关于 $x$ 的一次函数。所以 $p(A)$ 是一个关于 $x$ 的不超过 $n$ 次多项式。对 $2^n$ 种情况求和，还是关于 $x$ 的不超过 $n$ 次多项式。

一个值得关注的事情是，设 $pre_i = \sum_{j \le i} a_j$。当 $x \le pre_i$ 时概率是关于 $x$ 的一次函数，$> x$ 时概率是常数。所以本质上要把 $x$ 分为 $n$ 段去算，同一段内 $p(A)$ 是相同的，$f_x = Z(x)$ 的这个 $Z$ 也是相同的。

所以我们相当于知道了 $Z$，求出 $\sum_{x=pre_{i-1}+1}^{pre_i} Z(x)$。

所以我们可以设 $dp_{i,j}$ 为一个关于 $x$ 的多项式，记录它的系数。转移是 $O(n)$ 的，因为要乘上一个一次函数。不同的段对应的其实是 DP 终点不同，发现可以共用同一个 $dp_{i,j}$。然后你就只需要求出：$\sum_{x=1}^n x^k$。这是经典的拉格朗日插值优化问题。

其实你可以直接把 $x$ 挂进 $dp_{i,j}$ 里算的，然后使用拉格朗日插值求出 $Z(x)$ 的前缀和。后者是关于 $x$ 的 $n+1$ 次多项式，需要 $n+2$ 个点值。

我选择了后者，因为它实现起来更加方便。

复杂度 $O(n^3)$。我猜赛时没人过。

所以什么时候我能给科大国创出题啊 /kel

哎拉插常数太大了，拼尽全力卡进了 1 秒。

代码：

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=500+10,MOD=1e9+7;
int n,m,a[MAXN],pre[MAXN],inv[MAXN],dp[MAXN][MAXN],E[MAXN][MAXN];
ll qpow(ll base,int p) {
	ll ans=1;
	while(p) {
		if(p&1) ans=ans*base%MOD;
		base=base*base%MOD,p>>=1;
	}
	return ans;
}
void solve(int v) {
	dp[n+1][0]=1;
	int ad=0;
	roff(i,n,1) {
		ffor(j,0,n-i+1) dp[i][j]=0;
		ffor(j,0,n-i+1) {
			ll p=1ll*(pre[i]-v+1)%MOD*inv[i]%MOD;
			dp[i][j+1]=(dp[i][j+1]+dp[i+1][j]*p)%MOD;
			p=(1-p)%MOD; 
			dp[i][max(0,j-1)]=(dp[i][max(0,j-1)]+dp[i+1][j]*p)%MOD;
		}
		ll p=1ll*(pre[i]-v+1)%MOD*inv[i]%MOD;
		ad=(ad+p)%MOD,E[i][v]=2*ad%MOD;
		ffor(j,0,n-i+1) E[i][v]=(E[i][v]-1ll*dp[i][j]*(j-min(i-1,j)))%MOD;
	}
	return ;
}
int tot;
pair<int,int> vc[MAXN];
inline int lagrange(const int x1,const int x2) {
	int ans=0;
	ffor(id,1,tot) {
		auto pr=vc[id];
		ll mul,mul1=pr.second,mul2=pr.second,div=1;
		ffor(j,1,tot) if(j!=id) {auto npr=vc[j]; mul1=(x1-npr.first)*mul1%MOD,mul2=(x2-npr.first)*mul2%MOD,div=(pr.first-npr.first)*div%MOD;}
		mul=(mul1-mul2)%MOD,mul=mul*qpow(div,MOD-2)%MOD;
		ans=(ans+mul)%MOD;
	}
	return ans;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	ffor(i,1,n) cin>>a[i],pre[i]=pre[i-1]+a[i];
	ffor(i,1,n) inv[i]=qpow(pre[i],MOD-2);
	ffor(v,1,n+2) solve(v);
	ffor(i,1,n) ffor(j,1,n+2) E[i][j]=(E[i][j]+E[i][j-1])%MOD;
	int ans=0;
	ffor(i,1,n) {
		tot=0;
		ffor(j,1,n+2) vc[++tot]={j,E[i][j]};
		ans=(ans+lagrange(pre[i],pre[i-1]))%MOD;
	}
	cout<<(ans%MOD+MOD)%MOD;
	return 0;
}