[Luogu 4707] 重返现世

Posted on | Edited on | In , | Views:

前言

这篇文章的前置知识是Min_Max容斥，不会的同学可以先看一下我的另一篇博客
Min-Max容斥学习笔记
里面有详细的证明。

题目链接

Luogu 4707 重返现世

做法

这道题实际上就是要就是要我们求全集合出现第$n-k+1$大元素的期望时间。
直接套用kth Min-Max容斥的结论。
$E(kthMax(S))=\sum_{S’\subseteq S}E(Min(S’))*(-1)^{|S’|-k}*\binom{|S’|-1}{k-1}$
$E(Min(S’))=\frac{m}{\sum_{i\in S’}P(i)}$
发现m的范围并不大，那么我们考虑dp
令$sum(S)$表示$\sum_{i\in S}P(i)$，$U$表示全集
$g_{i,j}$表示对于集合S，$|S|=i$，$sum(S)=j$的方案数。
转移只要考虑每次加进来一个数是否放到集合中就行了，答案的计算应该也是显然的，这里不多赘述了。
但是这样dp的复杂度是$O(n^2*m)$的，难以接受。
观察到还有$|n-k|\le 10$的限制条件，考虑改变dp状态
$f_{i,j}$表示对于集合S，$sum(S)=i$，出现第j大元素的期望时间的总和，显然$1 \le j \le |n-k|$
但是直接求期望时间不方便处理，考虑把期望时间拿掉。
用式子写出来
$f_{i,j}=\sum_{S’ \subseteq U}(-1)^{|S’|-j}*\binom{|S’|-1}{j-1}*[sum(S’)=i]$
考虑加入第t个物品:
如果不加入，则直接继承答案
如果加入的话，答案应该和$f_{i-p[t],j}$有关。
仍然用$g_{i,j}$表示对于集合S，$|S|=i$，$sum(S)=j$的方案数。
考虑展开$f_{i-p[t],j}$，把枚举集合变为枚举集合的大小。
那么$f_{i-p[t],j}=\sum_{k=1}^{n}g_{k,i-p[t]}*\binom{k-1}{j-1}*(-1)^{k-j}$
再考虑$\Delta f_{i,j}$，枚举转移过来的集合的大小k
$\Delta f_{i,j}=\sum_{k=1}^{n}g_{k,i-p[t]}*\binom{k}{j-1}*(-1)^{k-j+1}$
两个式子做加法
$\Delta f_{i,j}+f_{i-p[t],j}=\sum_{k=1}^{n}g_{k,i-p[t]}*\binom{k}{j-1}*(-1)^{k-j+1}+\sum_{k=1}^{n}g_{k,i-p[t]}*\binom{k-1}{j-1}*(-1)^{k-j}$
后面一项添个-1，将公因式提取一下得到
$\Delta f_{i,j}+f_{i-p[t],j}=\sum_{k=1}^{n}g_{k,i-p[t]}*[\binom{k}{j-1}-\binom{k-1}{j-1}]*(-1)^{k-j+1}$
也就是$\sum_{k=1}^{n}g_{k,i-p[t]}*\binom{k-1}{j-2}*(-1)^{k-j+1}$
而$(-1)^{k-j+1}=(-1)^{k-j-1}$
那么$\sum_{k=1}^{n}g_{k,i-p[t]}*\binom{k-1}{j-2}*(-1)^{k-j+1}=f_{i-p[t],j-1}$
所以我们dp就可以递推了，枚举第$t$个物品是否加入，滚动一下，用$f’$表示枚举到第$t-1$个物品时的状态。
$f_{i,j}=f’_{i,j}-f’_{i-p[t],j}+f’_{i-p[t],j-1}$
再考虑一下临界状态，直接代入可以知道$f_{p[t],1}=1$，所以只要$f_{0,0}=1$就行了，实际上$j=0$没有意义，所以其他时候不用转移。
最后算答案的时候也很简单。
枚举$i$，令$j=k$，$ans+=\frac{f[i][j]*m}{j}$就好了

复杂度$O(n*m*|n-k|)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (10005)
using namespace std;
int n,K,m,d,ans;
const int P=998244353;
int a[N],f[2][N][11],inv[N]; 
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b);
}
int main(){
    read(n),read(K),read(m);
    K=n-K+1;
    inv[0]=inv[1]=1;
    for (int i=2;i<=m;i++) inv[i]=(1ll*-P/i*inv[P%i]%P+P)%P;
    for (int i=1;i<=n;i++) read(a[i]);
    for (int i=1;i<=n;i++){
        f[d][0][0]=1;
        d^=1;
        for (int j=1;j<=m;j++){
            for (int k=1;k<=K;k++){
                f[d][j][k]=f[d^1][j][k];
                if (j>=a[i]){
                    f[d][j][k]=Inc(f[d][j][k],f[d^1][j-a[i]][k-1]);
                    f[d][j][k]=Inc(f[d][j][k]-f[d^1][j-a[i]][k],P);
                }
            }
        }
    }
    for (int j=0;j<=m;j++){
        ans=Inc(ans,1ll*f[d][j][K]*inv[j]%P*m%P);
    }
    printf("%d",ans);
    return 0;
}