ZigZagK的博客
[扩展Min-Max容斥+DP]洛谷4707【重返现世】题解
2019年2月2日 16:24
洛谷
查看标签

题目概述

有 $n$ 种物品,每单位时间出现 $i$ 物品的概率为 $p_i$ ,求恰好出现 $K$ 个不同物品的期望时间。

解题报告

Min-Max容斥?但是出现 $K$ 个是什么鬼啊。这里要用到扩展Min-Max容斥,令 $max_k(S)$ 表示集合 $S$ 的第 $k$ 大值,$min(S)$ 表示集合 $S$ 的最小值,设容斥系数为 $f(|T|)$ ,使得:

$$ max_k(S)=\sum_{T\subseteq S}f(|T|)min(T) $$

Min-Max容斥的推导过程,我们可以得到:

$$ f(x+1)=\sum_{i=0}^{x}(-1)^{x-i}{x\choose i}[i=k-1]=(-1)^{x-(k-1)}{x\choose k-1}\\ f(x)=(-1)^{x-k}{x-1\choose k-1} $$

所以:

$$ max_k(S)=\sum_{T\subseteq S}(-1)^{|T|-k}{|T|-1\choose k-1}min(T) $$


先给出题人跪了Orz……这题太精妙了……

题目里的 $K$ 是第 $K$ 小而不是第 $K$ 大,所以先让 $K=n-K+1$ ,会得到 $K\le 11$ 这个可疑的范围。

先不管 $K$ ,由于 $n\le 1000$ 所以我们显然只能考虑长度而不是集合,于是:

$$ ans=\sum_{i=K}^{n}(-1)^{i-K}{i-1\choose K-1}sum(i) $$

其中 $sum(i)=\sum_{|T|=i}min(T),min(T)={1\over\sum_{i\in T}p_i}$ ,关键问题是 $sum(i)$ 怎么求。

直接维护假的不行,因为维护的是一堆倒数和,不可合并。

由于又一个可疑的范围 $m\le10000$ ,所以考虑把所有 $\sum p_i$ 存起来,这样就不需要考虑倒数和合并了。

定义 $f_{t,i,j}$ 表示前 $t$ 个物品选了 $i$ 个物品体积(把 $p_i$ 当成体积)为 $j$ 的方案数,$O(n^2m)$ 求出 $f$ 之后 $sum(i)$ 就很好求了。

但是止步于此了,因为这个DP的状态数转移数转移效率都是不能优化的了,所以我们需要另外想办法。


接下来是神仙思路:由于 ${n\choose m}={n-1\choose m-1}+{n-1\choose m}$ ,这让我们意识到答案式子是可以像组合数一样合并出来的!

定义 $F_{t,j,k}​$ :

$$ F_{t,j,k}=\sum_{i=k}^{n}(-1)^{i-k}{i-1\choose k-1}f_{t,i,j} $$

由于 $f_{t,i,j}=f_{t-1,i,j}+f_{t-1,i-1,j-p_t}$ ,所以我们把相关的 $F​$ 写出来看看:

$$ F_{t-1,j,k}=\sum_{i=k}^{n}(-1)^{i-k}{i-1\choose k-1}f_{t-1,i,j}\\ \begin{aligned} F_{t-1,j-p_t,k}&=\sum_{i=k}^{n}(-1)^{i-k}{i-1\choose k-1}f_{t-1,i,j-p_t}\\ &=\sum_{i=k+1}^{n+1}(-1)^{i-1-k}{i-2\choose k-1}f_{t-1,i-1,j-p_t}\\ &=-\sum_{i=k}^{n}(-1)^{i-k}{i-2\choose k-1}f_{t-1,i-1,j-p_t} \end{aligned} $$

不难发现我们缺了 ${i-2\choose k-2}$ ,于是还有一个:

$$ \begin{aligned} F_{t-1,j-p_t,k-1}&=\sum_{i=k-1}^{n}(-1)^{i-(k-1)}{i-1\choose k-2}f_{t-1,i,j-p_t}\\ &=\sum_{i=k}^{n+1}(-1)^{i-k}{i-2\choose k-2}f_{t-1,i-1,j-p_t}\\ \end{aligned} $$

所以得到 $F_{t,j,k}=F_{t-1,j,k}+F_{t-1,j-p_t,k-1}-F_{t-1,j-p_t,k}​$ 。

最后还有个边界问题,因为当 $k=1$ 的时候就没有 ${i-1\choose k-1}={i-2\choose k-2}+{i-2\choose k-1}$ 这个式子了,为了统一我们可以强行定义 ${i\choose -1}=0(i\ge0),{-1\choose -1}=1$ ,那么初值就是:

$$ f_{0,0,0}=1,F_{0,0,0}=\sum_{i=0}^{n}(-1)^i{i-1\choose -1}f_{0,i,0}=(-1)^0{-1\choose -1}f_{0,0,0}=1 $$

这样就做到 $O(nmk)$ 了……

示例程序

因为爆空间,所以像背包那样维护就行了,当然也可以滚动数组。

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000,maxm=10000,maxk=10,MOD=998244353;

int n,m,K,p[maxn+5],f[maxm+5][maxk+5],ans;

inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&K,&m);K=n-K+1;for (int i=1;i<=n;i++) scanf("%d",&p[i]);
    for (int i=f[0][0]=1;i<=n;i++)
        for (int j=m;j>=p[i];j--)
            for (int k=1;k<=K;k++)
                AMOD(f[j][k],f[j-p[i]][k-1]),AMOD(f[j][k],MOD-f[j-p[i]][k]);
    for (int i=1;i<=m;i++) AMOD(ans,(LL)m*Pow(i,MOD-2)%MOD*f[i][K]%MOD);
    return printf("%d\n",ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!