P4707 重返现世

巧妙的 DP 题目。

设 $k^{'} = n - k - 1$ ，并接下来都是用 $k^{'}$ 。设每种材料被收集的时间为 $t_{i}$ ，相当于求 $E (kth {max}_{i = 1}^{n} t_{i})$ 。max 显然不好直接求，考虑 min-max 容斥得到：

E (kth max_{i \in S} t_{i}) = \sum_{T \subseteq S} (- 1)^{| T | - k} (\binom{| T | - 1}{k - 1}) E (min_{i \in T} t_{i})

其中 $E (min_{i \in S} t_{i}) = \frac{m}{\sum_{i \in S} p_{i}}$ 。考虑一个暴力 DP，设状态 $f (i, j)$ 表示选择 $i$ 种材料， $\sum_{i \in S} p_{i} = j$ 的方案数。因为需要每次枚举所有材料。这样的时间复杂度 $O (n^{2} m)$ ，不能通过。

注意到 $k$ 是很小的。考虑 $k$ 压进去。于是我们直接求容斥系数 $\sum_{\sum_{i \in S} p_{i} = j} (- 1)^{| T | - k} (\binom{| T | - 1}{k - 1})$ 。因为需要计算 $\frac{m}{f (S)}$ 的贡献， $\sum_{i \in S} p_{i}$ 还是需要压进状态里，于是考虑设计状态 $f (i, j, k)$ 表示考虑前 $i$ 个数， $\sum_{i \in S} p_{i} = j$ ，关于 $k$ 的容斥系数。但是处理组合数似乎令人头疼，尝试利用 $(\binom{n}{m}) = (\binom{n - 1}{m}) + (\binom{n - 1}{m - 1})$ ，拆一下 $| T |, k$ 的容斥系数，得到：

\begin{aligned} (1) & (- 1)^{| T | - k} (\binom{| T | - 1}{k - 1}) \\ (2) & = & (- 1)^{| T | - k} ((\binom{| T | - 2}{k - 1}) + (\binom{| T | - 2}{k - 2})) \\ (3) & = & - (- 1)^{| T | - k - 1} (\binom{| T | - 2}{k - 1}) + (- 1)^{| T | - k} (\binom{| T | - 2}{k - 2}) \end{aligned}

拆出来的两个是 $| T | - 1, k$ 和 $| T | - 1, k - 1$ 的容斥系数！这就很棒了，因为这个递推关系与 $| T |$ 具体值无关，我们就不用枚举每一种材料了。我们容易得到状态转移方程：

f (i, j, k) = f (i - 1, j, k) - f (i - 1, j - p_{i}, k) + f (i - 1, j - p_{i}, k - 1)

需要注意的是对边界的处理。有用的状态只有 $k > 0$ 。 $k = 0$ 作为边界，只会被贡献到 $f (i + 1, p_{i}, 1)$ ，新选的产生的容斥系数为 $(- 1)^{1 - 1} (\binom{0}{0}) = 1$ ，于是边界应为 $f (i, 0, 0)$ 。或者换一种角度，从定义出发， $f (i, 0, 0) = (- 1)^{0 - 0} (\binom{- 1}{- 1}) = 1$ ，这里的组合数涉及到负数，需要用到扩展的定义，但依然满足上面的递推式。

滚动数组倒序枚举 $j$ 能够压掉 $i$ 这一维的空间。总的时间复杂度为 $O (n m k)$ 。

代码极短，并且十分好写。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e3+10,M=1e4+10,K=15,mod=998244353;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,k;
int p[N];

int f[M][K];
inline int adj(int x){return  x>=mod?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
    int res=1;
    while(k)
    {
        if(k&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}
int main()
{
    read(n,k,m);
    k=n-k+1;
    for(int i=1;i<=n;i++)read(p[i]);
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=p[i];j--)
            for(int l=k;l;l--)
                f[j][l]=adj(adj(f[j][l]+f[j-p[i]][l-1])-f[j-p[i]][l]+mod);
    int ans=0;
    for(int i=1;i<=m;i++)ans=adj(ans+1ll*qpow(i)*f[i][k]%mod);
    printf("%lld\n",1ll*m*ans%mod);
    return 0;
}