题解 P4707 【重返现世】

广告:[Min-Max容斥小记](https://www.luogu.org/blog/command-block/min-max-rong-chi-xiao-ji) 好,我假设你们都会Min-Max容斥了。 题意:每秒按固定概率出现物品,求收集到$k$个物品的期望时间。 这道题还是很有难度的,这个黑牌不亏(~~或者是我的dp太菜了~~……) 分析:我们设集合$S$为某些物品的集合,物品的权值为第一次出现时间。 那么$E(min(S))$就是这些物品中有其中一个出现的期望时间。 每一次得到$S$中物品的概率是$\sum\limits_{i∈S}p_i$,那么期望时间就是$\dfrac{1}{\sum\limits_{i∈S}p_i}$。 我们能求$E(min(S))$了,我们再想想,$E(Kthmin(U))$($U$是全集)不就相当于期望耗时吗? 我们令下文的$k=n-k+1$,求的就是$E(Kthmax(U))$了,同时在题目中看到,这里的$k<=11$。 套用扩展Min-Max容斥,我们就得到了式子: $ANS=\sum\limits_{T∈S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}E(\min(T))$ 但是这里的$n<=1000$不能直接$O(2^n)$统计…… 我们观察发现,$m<=10000$,一道数数题居然限制值域?没准是复杂度和$m$有关的$dp$。 容易想到一个个加入物品,先观察求和的式子,变量只有$|T|,E(min(T))$两个。 $E(min(T))$和$\sum\limits_{i∈T}p_i$直接相关。 那就都设到状态里面呗,$f[i][j][k]$表示前$i$个物品,选了$j$个,$\sum\limits_{i∈T}p_i=k$的方案数。 到最后把方案数乘以对应权值,求个和就是答案了。 那么转移的话,可以考虑选或不选当前物品,选的话: $f[i][j+1][k+p[i]]+=f[i-1][j][k];$ 不选则原封不动$f[i][j][k]+=f[i-1][j][k];$ 为了节省空间,可以把第一维滚掉。 复杂度$O(n^2m)$,可以拿到$70$分。 我们发现每个东西的贡献=($E(\min(T))*|T|$相关的一坨东西*方案数)。 那么我们可以直接把这个式子的一部分作为dp权值,就可以减少维数了,降过维之后,由于我们把未知量强行塞入了dp权值里面,很有可能是无法直接转移的,还要在状态上加维数。 这种技巧称作“权值包含状态”或者叫“换维打击”,把维数藏在权值里。 发现$k<=11$,那么这个新的维度很有可能就是$k$了。 到底是把$E(\min(T))$加入权值还是$(-1)^{|T|-k}\dbinom{|T|-1}{k-1}$呢? 第一,前者是某个东西的倒数,相加将会变得十分恶心; 第二,只有后者与$k$相关。那么我们把后者加入状态,看看会发生什么…… 设$f[i][j]$表示前$i$个物品,$\sum\limits_{i∈T}p_i=j$的$(-1)^{|T|-k}\dbinom{|T|-1}{k-1}$和。 转移的话,还是可以考虑选或不选当前物品$x$: 不选$x$则原封不动$f[i][j]+=f[i-1][j];$ 强制选的话,转移开始不对劲了:$f[i][j+p[i]]=f[i-1][j]?$ 可以得到,$\sum(-1)^{|T|-k}\dbinom{|T|-1}{k-1}$,加入了$x$之后就会变成$\sum(-1)^{|T|-k+1}\dbinom{|T|}{k-1}$ 由于我们没有记录$|T|$,虽然$-1$很好办,但是这个组合数是很难处理的…… 我们把这个组合数拆开,得到$\sum(-1)^{|T|-k+1}\dbinom{|T|}{k-1}=(-1)^{|T|-k+1}\left[\dbinom{|T|}{k-2}+\dbinom{|T|-1}{k-1}\right]$ 再给它拆分开,得到$\sum(-1)^{|T|-k-1}\dbinom{|T|}{k-2}-\sum(-1)^{|T|-k}\dbinom{|T|-1}{k-1}$ 我一看,后面不就是$f[i-1][j]$吗? 前面的那部分$k$有些不对头,看来还要记录$k$这一维,我们猜对了!(顺便Orz出题人) 正确姿势: 设$f[i][j][k]$表示前$i$个物品,$\sum\limits_{i∈T}p_i=j$,而且$k$如所设的$(-1)^{|T|-k}\dbinom{|T|-1}{k-1}$和。 考虑选或不选当前物品$x$: 不选$x$则原封不动$f[i][j][k]+=f[i-1][j][k];$ 强制选的话:继承上面的推导$f[i][j+p[i]][k]+=$ $\sum(-1)^{|T|-k-1}\dbinom{|T|}{k-2}+\sum(-1)^{|T|-k+1}\dbinom{|T|-1}{k-1}$ $=f[i-1][j][k-1]-f[i-1][j][k]$,皆大欢喜! 边界问题怎么办?$\dbinom{-1}{-1}=0$所以$f[0][0][0]=1;$即可。 为了省空间,仍然需要把第一维滚掉。 注意有$p_i=0$的情况。 **Code:** ```cpp #include<algorithm> #include<cstdio> #include<map> #define mod 998244353 #define MaxM 10050 #define mod 998244353 using namespace std; long long f[MaxM][15],ans; int n,kk,m,p[MaxM]; long long powM(long long a,long long t) { long long ans=1; while(t){ if (t&1)ans=ans*a%mod; a=a*a%mod; t>>=1; }return ans; } int main() { scanf("%d%d%d",&n,&kk,&m);kk=n-kk+1; for (int i=1;i<=n;i++)scanf("%d",&p[i]); f[0][0]=1; for (int i=1;i<=n;i++) if (p[i]) for (int j=m-p[i];j>=0;j--) for (int k=kk;k;k--) f[j+p[i]][k]=(f[j+p[i]][k]+f[j][k-1]-f[j][k])%998244353; for (int j=1;j<=m;j++) ans=(ans+f[j][kk]*m%mod*powM(j,mod-2))%mod; printf("%lld",(ans+mod)%mod); return 0; } ```