【洛谷4707】重返现世(kth Min-Max容斥+动态规划)

点此看题面

大致题意: 有\(n\)种物品,每个单位时间生成一种物品,其中第\(i\)种物品有\(\frac{p_i}{\sum_{t=1}^np_t}\)的概率生成。求生成\(k\)种物品的期望时间。

前言

这道题来自\(XZY\)神仙的洛谷智推。

能被智推到这种神仙题,充分体现出连人工智能都已经充分认识到\(XZY\)的神仙本质,在此疯狂膜拜\(XZY\)神仙\(\%\%\%\)。

我这个蒟蒻想了快两个小时都没做出来,最后还是去翻了题解,深深感觉到自己的弱小。

\(kth\ Min-Max\)容斥

对于这道题,首先你需要知道一个公式,即\(kth\ Min-Max\)容斥。

考虑\(Min-Max\)容斥的公式为:

\[E(Max(S))=\sum_{T∈S}(-1)^{|T|-1}E(Min(T))\]

而\(kth\ Min-Max\)容斥的公式就是\(Min-Max\)容斥公式的推广,两者十分相像:

\[E(kth\ Max(S))=\sum_{T∈S}(-1)^{|T|-k}C_{|T|-1}^{k-1}E(Min(T))\]

这个公式是我们做这道题的基础。

同时需要注意,题目中询问生成\(k\)种物品的期望,并非\(kth\ Max\),而是\((n-k+1)th\ Max\)(一开始就被这个坑了还自以为想出了正解......)。

为了方便起见,我们可以直接把读入的\(k\)修改为\(n-k+1\),则注意题目数据范围里特殊给出的\(n-k\le10\),此时就变成了\(k\le11\)。

动态规划

考虑\(E(Min(T))\)是个什么东西。

根据其定义,我们知道,就是取到点集\(T\)中任意一点的期望。

显然,设\(sum_T\)为点集\(T\)中所有\(p\)的总和,则取到点集\(T\)中任意一点的概率就等于\(\frac{sum_T}m\)。

则期望显然就等于\(\frac m{sum_T}\)。

把这个东西代回到式子中,就得到:

\[E(kth\ Max(S))=\sum_{T∈S}(-1)^{|T|-k}C_{|T|-1}^{k-1}\frac m{sum_T}\]

然后我们就可以发现,在这个式子中,与\(T\)有关的项只有\(|T|\)和\(sum_T\)。

所以我们似乎可以考虑,进行一个与\(|T|\)和\(sum_T\)有关的动态规划。

于是就可以设状态\(f_{i,j,t}\)表示在前\(i\)种物品中选择若干个物品,并使得\(sum_T=t\),此时的\((-1)^{|T|-j}C_{|T|-1}^{j-1}\)的值的总和。

这个东西怎么转移呢?

如果我们不选当前物品,显然有\(f_{i,j,t}=f_{i-1,j,t}\)。

如果我们选当前物品,则根据组合数的一个基本公式\(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\)可得:

\[f_{i,j,t}=(-1)^{|T|-j}C_{|T|-1}^{j-1}=(-1)^{|T|-j}C_{|T|-2}^{j-1}+(-1)^{|T|-j}C_{|T|-2}^{j-2}\]

也就是:

\[f_{i,j,t}=-(-1)^{(|T|-1)-j}C_{(|T|-1)-1}^{j-1}+(-1)^{(|T|-1)-(j-1)}C_{(|T|-1)-1}^{(j-1)-1}\]

观察这个式子便可以发现:

\[f_{i,j,t}=-f_{i-1,j,t-p_i}+f_{i-1,j-1,t-p_i}\]

于是我们就得到了转移方程(是不是无比玄学......)。

而最后答案显然就是\(\sum_{t=1}^mf_{n,k,t}\cdot\frac mt\)。

关于内存

显然这个数组开不下。

发现这个东西跟背包似乎长得有些类似,于是我们可以利用和背包类似的想法,把第一位\(i\)去掉,而之后两维倒着枚举进行转移。

关于边界

边界的设置似乎十分玄学。

大体就是:

\[f_{j,0}=\begin{cases}0&(j=0)\\-1&(j>0)\end{cases}\]

至于为什么,是因为这么设置边界刚好能使得最初的状态正确,可以自己去推一推。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 1000
#define M 10000
#define K 10
#define X 998244353
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
using namespace std;
int n,m,k,a[N+5],f[K+5][M+5];
I int Qpow(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
I int XSum(CI x,CI y) {return x+y>=X?x+y-X:x+y;}
int main()
{
    RI i,j,t,ans=0;for(scanf("%d%d%d",&n,&k,&m),k=n-k+1,i=1;i<=n;++i) scanf("%d",a+i);//读入时把k修改为n-k+1
    for(j=1;j<=k;++j) f[j][0]=X-1;for(i=1;i<=n;++i)//设边界
        for(j=k;j;--j) for(t=m;t>=a[i];--t) f[j][t]=XSum(f[j][t],XSum(f[j-1][t-a[i]],X-f[j][t-a[i]]));//动态规划转移
    for(t=1;t<=m;++t) ans=(1LL*f[k][t]*m%X*Qpow(t,X-2)+ans)%X;return printf("%d",ans),0;//统计答案
}
上一篇:简易版第k大(权值线段树+动态开点模板)


下一篇:LeetCode - 703. Kth Largest Element in a Stream