洛谷 P4707 - 重返现世(扩展 Min-Max 容斥+背包)

题面传送门

首先看到这种求形如 \(E(\max(T))\) 的期望题,可以套路地想到 Min-Max 容斥 \(\max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-1}\min(T)\),将其转化为容易计算的 \(E(\min(T))\) 进行计算。

不过这题有些不同的一点是我们要求的是第 \(k\) 大而不是最大值,无法直接 Min-Max,这时就要用到一个叫扩展 Min-Max 的东西了,首先抛出式子:\(\max_k(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\times\min(T)\),其中 \(\max_k(S)\) 为 \(S\) 中第 \(k\) 大的值。考虑证明,其实和 Min-Max 证明那一套差不多罢,考虑将 \(S\) 中的数从小到大排序 \(a_1,a_2,\cdots,a_n\),我们按照套路枚举 \(\min(T)=a_i\),那么前面那一坨系数等价于选出 \(a_{i+1},a_{i+2}\cdots,a_{n}\) 的一个子集 \(T\),再从 \(T\) 中选 \(k-1\) 个数,贡献 \((-1)^{|T|+1-k}\)(指数上的 \(+1\) 是因为真正的 \(T\) 是我们选出的 \(T\) 与 \(\{a_i\}\) 的并),所有这样的选法的贡献之和,那么我们就考虑换个角度,枚举选出的 \(k-1\) 个数,显然若 \(i>n-k+1\) 贡献就是 \(0\),否则有 \(\dbinom{n-i}{k-1}\) 种选法,再枚举在 \(T\) 中却不再选出的 \(k-1\) 个数的部分 \(S\),那么 \(S\) 显然可以为剩余 \(n-i-(k-1)\) 个数的任意一个子集,这部分的贡献就是 \(\sum\limits_{j=0}^{n-i-(k-1)}\dbinom{n-i-(k-1)}{j}(-1)^{j+(k-1)+1-k}=\sum\limits_{j=0}^{n-i-(k-1)}\dbinom{n-i-(k-1)}{j}(-1)^{j}=[i=n-k+1]\),也就是说只有 \(i=n-k+1\) 时候这部分贡献为 \(1\),其余贡献都是 \(0\),而 \(i=n-k+1\) 时前面那部分贡献刚好也是 \(1\),因此 \(\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\times\min(T)=a_{n-k+1}\),证毕。

接下来考虑原题,首先本题 \(k\) 的意义实际上是 \(E(\min_k(T))\),因此我们需做一个简单的转化将其变为 \(E(\max_k(T))\) 的形式,即 \(k\leftarrow n-k+1\),而 \(|n-k|\le 10\),也就是说变换后的 \(k\le 11\),刚好。然后考虑怎样计算 \(\max_k(S)\) 的表达式,显然 \(E(\min(T))=\dfrac{m}{\sum\limits_{x\in T}p_x}\)(这里我们假设 \(T\) 为下标集合而不是下表对应的 \(p_i\) 的集合),也就是说虽然集合 \(T\) 的数量可以达到 \(2^n\),但是我们可以将所有 \(E(\min(T))\) 相同的集合 \(T\) 划分在一个等价类中,那么这些集合最多划分为 \(m\) 个等价类,这样就可以 \(dp\) 了,记 \(dp_{i,j,s}\) 为考虑了前 \(i\) 个数,选中的集合上述计算式中的 \(k=j\),\(\sum\limits_{x\in T}p_x=s\),所有这样的集合 \(T\) 的 \((-1)^{|T|-j}\dbinom{|T|-1}{j-1}\) 之和,考虑转移,若 \(i\) 不选择那么显然有 \(dp_{i,j,s}\leftarrow dp_{i-1,j,s}\),否则我们相当于在 \(|T|\) 中加入了一个元素 \(p_i\),应当从 \(dp_{i-1,*,s-p_i}\) 转移来,我们假设 \(T\) 满足 \(T\) 只由前 \(i\) 个数组成,并且 \(\sum\limits_{x\in T}p_x=s-p_i\),那么贡献就说 \(\sum(-1)^{|T|+1-j}\dbinom{|T|}{j-1}\),我们把前面指数上的 \(1\) 提出来,变为 \(\sum-(-1)^{|T|-j}\dbinom{|T|}{j-1}\),再套个组合数递推公式,\(\sum-(-1)^{|T|-j}(\dbinom{|T|-1}{j-1}+\dbinom{|T|-1}{j-2})\),噫,好!这下这东西就容易计算了,因为显然它等于 \(\sum-(-1)^{|T|-j}\dbinom{|T|-1}{j-1}+(-1)^{|T|-j+1}\dbinom{|T|-1}{j-2})\),而你稍微转化一下就能变成 \(-dp_{i-1,j-1,s-p_i}+dp_{i-1,j-2,s-p_i}\),这样就可以在常数时间内实现 \(dp\) 的转移了,即:\(dp_{i,j,s}=dp_{i-1,j,s}-dp_{i-1,j-1,s-p_i}+dp_{i-1,j-2,s-p_i}\)。当然每个数也可以单独成一组,即如果 \(j=1\),那么 \(dp_{i,j,p_i}\leftarrow dp_{i,j,p_i}+1\)。

时空复杂度均为 \(nmk\),由于这题直接开数组大小会达到 \(10^8\),会 \(\text{MLE}\),因此需要用滚动数组/01背包倒序枚举的套路将第一维优化掉,我相信做这一题的人应该不至于不能理解这一步罢……因此就不再赘述了。

代码异常简洁……

const int MAXK=11;
const int MAXM=1e4;
const int MOD=998244353;
int n,k,m,dp[MAXK+5][MAXM+5],inv[MAXM+5];
int main(){
scanf("%d%d%d",&n,&k,&m);k=n+1-k;
for(int i=(inv[1]=1)+1;i<=m;i++) inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1,t;i<=n;i++){
scanf("%d",&t);
for(int l=m;l>=t;l--) for(int j=k;j;j--){
dp[j][l]=(dp[j][l]+(-dp[j][l-t]+dp[j-1][l-t]+MOD)%MOD)%MOD;
} dp[1][t]=(dp[1][t]+1)%MOD;
} int ans=0;
for(int i=1;i<=m;i++) ans=(ans+1ll*dp[k][i]*inv[i]%MOD*m)%MOD;
printf("%d\n",ans);
return 0;
}
上一篇:Luogu P4707 重返现世 (拓展Min-Max容斥、DP)


下一篇:转载:Linux内核参数的优化(1.3.4)《深入理解Nginx》(陶辉)