题解 P4707 【重返现世】

首先可以发现题目要求的为：

E(max(S)_k)

套用拓展min-max

得到：

E(max(S)_k)=\sum_{T\subseteq S}\dbinom{|T|-1}{k-1}(-1)^{|T|-k}E(min(T))

我们知道原来要求的是全集合中出现时间排第k的元素，由于变成了正过来看，此时的k变成了n-k+1，换而言之非常小，只有(11)

我们知道一个集合每次操作出现一个属于它的元素的概率为：

e(S)=\sum_{i\in S}\dfrac{p_i}{m}

于是我们知道期望时间为：

\sum_{i=1}^{\infty} e(S)(1-e(S))^{i-1}=\dfrac{1}{e(S)}

于是现在我们得到了一个复杂度为O(2^n)的做法，暴力枚举子集，对于每个集合求出此式子并计算贡献

然后我就不会了....

接下来看来需要一点魔法了...

我们来看下这个式子：

E(max(S)_k)=\sum_{T\subseteq S}\dbinom{|T|-1}{k-1}(-1)^{|T|-k}E(min(T))

考虑一个固定的集合大小|T|，其分配的系数相同均为\dbinom{|T|-1}{k-1}(-1)^{|T|-k}

则我们只需要求出\sum_{|T|=x}E(min(T))

注意到E(min(T))=\dfrac{1}{e(S)}于是我们可以给dp加一个维度记录\sum p=e(S)，这样只需要统计有多少个点满足\sum p=i,|T|=j

于是可以得到，不妨记dp_{i,j,k}表示考虑到前i个数，满足|T|=j,\sum p=k的集合数，则可以得到转移：

dp_{i,j,k}=dp_{i-1,j,k}+dp_{i-1,j-1,k-p_i}

于是这样便可以得到一个复杂度为O(n^2 m)的做法了...(代码比较简单就不放了)

于是问题在于如何优化复杂度？

我们发现转移已经是最优了，不能从这里下手于是只能从状态下手

由于k这一维度附带了一个\dfrac{1}{k}于是肯定是不能省略的，唯一的办法是把记录中的|T|给去掉试试

换而言之我们只统计，到第i个数，任意放满足\sum p=k的数前面安排的系数之和

考虑系数为：

\sum \dbinom{|T|-1}{k-1}(-1)^{|T|-k}

拆开试试？

\sum \dfrac{(|T|-1)!}{(k-1)!(|T|-k)!}(-1)^{|T|-k}

好像还是不行...

但是这个时候可以得到转移大致为：

dp_{i,j}=dp_{i-1,j}+...

这个奇怪的东西应该表示为：

对于dp_{i-1,j-p_i}的：

\sum \dbinom{|T|-1}{k-1}(-1)^{|T|-k}

首先可以注意到所有|T|\to |T|+1于是整体需要乘一个-1

注意到|T|\to |T|+1于是组合数变成了：

\dbinom{|T|}{k-1}

但是我们知道组合数可以递推所以有：

\dbinom{|T|}{k-1}=\dbinom{|T|-1}{k-1}+\dbinom{|T|-1}{k-2}

然而真正有趣的是这个式子可以放在一起一起递推，因为考虑计算dp时强制放入一个数则等价于|T|必然变大1，于是我们可以给dp增加一个维度k来计算dp系数

dp_{i,j,k}=dp_{i-1,j,k}+(-1)\times dp_{i-1,j-p_i,k}+(-1)^{2}\times dp_{i-1,j-p_i,k-1}

即：

dp_{i,j,k}=dp_{i-1,j,k}-dp_{i-1,j-p_i,k}+ dp_{i-1,j-p_i,k-1}

这个dp是真的超级棒！

接下来考虑边界条件，这个好像有点难，因为我们的dp是按照转移的需求设计，所以它存在的实际意义(在我看来)也是为了方便转移而存在的dp

考虑边界问题，我们知道

dp_{0,j,k}$的意义应该是：$\sum_{\sum p=j}\dbinom{|T|-1}{k-1}

于是考虑前面的数，唯一的一个\sum p=j是空集，即\sum p=0此时有|T|=0求的则是：

dp_{0,0,k}=\dbinom{-1}{k-1}

这个时候我们需要拓宽组合数的意义，你可以认为\dbinom{-1}{-1}=1而\dbinom{x}{y}在x<y的时候=0但x=y的时候为1，(这好像是下降幂定义组合数的那一套)，所以我们的边界应该是dp_{0,0,0}=1

当然转移的过程可以滚动数组整体复杂度O(nmk)

Code:

#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
int gi() {
    char cc = getchar() ; int cn = 0, flus = 1 ;
    while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
    while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
    return cn * flus ;
}
const int N = 1000 + 5 ; 
const int M = 10000 + 5 ; 
const int P = 998244353 ; 
int n, m, t, Ans, inv[M], p[N], dp[14][M] ; 
int fpow( int x, int k ) {
    int ans = 1, base = x ; 
    while( k ) {
        if( k & 1 ) ans = ans * base % P ; 
        base = base * base % P, k >>= 1 ; 
    } return ans ; 
}
signed main()
{
    n = gi(), t = n - gi() + 1, m = gi() ;
    rep( i, 1, n ) p[i] = gi() ; inv[0] = dp[0][0] = 1 ; 
    rep( i, 1, m ) inv[i] = fpow( i, P - 2 ) % P ;
    for( re int i = 1; i <= n; ++ i ) {
        for( re int k = m; k >= p[i]; -- k )
        for( re int j = t; j; -- j )
            dp[j][k] = ( dp[j - 1][k - p[i]] - dp[j][k - p[i]] + dp[j][k] + P ) % P ;
    }
    for( re int k = 0; k <= m; ++ k ) Ans = ( Ans + dp[t][k] * inv[k] % P ) % P ;  
    printf("%lld\n", Ans * m % P ) ;
    return 0 ;
}