P4707 重返现世

*终于弥补了缺陷

首先根据kthminmax反演和期望的线性性我们不难得出

$E(kmax(T))=\sum_{S \in T}(-1)^{|S|-k|}\binom{|S|-1}{k-1}E(min(T))$

这个式子的记法就是考虑minmax反演的本质,就是在排名上进行反演,恰好前1大等于至少前1大-至少前2大.....

同时"至少前k大"的取值就是第k大w

然后我们显然就能得出那个容斥系数qwq

但是这个组合数的形式好像不太优美,于是我们就有考虑这个前1大minmax反演的形式拿出来插值!

考虑这个E,大概率都是 $1/p$ 所以这个题就是 $\frac{m}{\sum p}$

所以这个题我们对于这个式子取值关键影响的只有选取的集合大小和p的和

也就是说我们只需要把这个 $f_{i,p}$ 表示选取集合大小为i,然后概率之和为p的方案数的数组求出来,然后再一起统计就好了

也就是说:容斥dp的一个核心在于把取值一样的求个贡献再一起加起来,不同的贡献很少所以这个很快

有些情况下直接出方案数就好了,但是这未免不太现实没有充分利用dp的强大之处:算权值和!!

所以本题考虑算 $(-1)^{|S|-k}\binom{|S|-1}{k-1}E$

首先-1很好做,直接写入转移,乘一下就好了,每次多选一个数就乘个-1

然后这个组合数,我们有递推公式 $\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$ ,而使用递推公式,我们的k是一定要写入状态的

观察发现这个就是选或者不选,同时选或者不选也对应了第三维E的转移代价 $f_{i-1,p-w_k}+f_{i,p}$

检查一下,我们现在是四维的,不太好,你会发现记录集合大小的好像就是为了-1和组合数

但是-1被我们直接写入转移系数了,组合数这个递推取决于选数的那一维!

所以我们不需要记录选的集合大小,于是我们的最后dp状态非常奇怪

$f_{i,j,k}$ 表示选了任意个数l, $(-1)^{l-k}\binom{l-1}{k-1}$ 的权值和!

于是我们有最后就是k=K的时候,K是n+1-k就是第K大

所以最后我们使用容斥dp,然后乘上m/p即可

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 998244353;
const int MAXN = 1e3 + 7;
const int MAXM = 1e4 + 7;
const int MAXD = 15;
int n, K, m, p[MAXN];
int f[MAXD][MAXM];
ll fac[MAXM], ifac[MAXM];
inline void add(int &x, int y) {
    x += y;
    if(x >= P)x -= P;
}

inline ll sub(int x, int y) {
    x -= y;
    if(x < 0)x += P;
    return x;
}

inline ll ksm(ll x, ll y) {
    ll ans = 1;
    while(y) {
        if(y & 1)ans = ans * x % P;
        x = x * x % P;
        y >>= 1;
    }
    return ans;
}

inline void init() {
    for(int i = 1; i <= K; ++i)f[i][0] = -1;
    fac[0] = 1;
    for(int i = 1; i <= m; ++i)fac[i] = fac[i - 1] * i % P;
    ifac[m] = ksm(fac[m], P - 2);
    for(int i = m - 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
    ifac[0] = 1;
    return ;
}

int main() {
    scanf("%d%d%d", &n, &K, &m);
    K = n + 1 - K;
    for(int i = 1; i <= n; ++i)scanf("%d", &p[i]);
    init();
    for(int i = 1; i <= n; ++i) {
        for(int j = m; j >= p[i]; --j) {
            for(int k = K; k; --k ) {
                add(f[k][j], sub(f[k - 1][j - p[i]], f[k][j - p[i]]));
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= m; ++i)add(ans, ifac[i] * f[K][i] % P * fac[i - 1] % P);
    printf("%lld\n", 1ll * ans * m % P);
    return 0;
}

夏晓光(loveJY)的博客

春姬的炫酷反演魔术