题目概述

有 $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;
}