Luogu4707 重返现世 min-max容斥、DP

kthMinMax的唯一模板？

首先你需要知道kth Min-Max定理的内容：\(kthmax(S) = \sum\limits_{T \subseteq S} (-1)^{|T| - k} \binom{|T| - 1}{k - 1}min(T)\)，证明与二项式反演相关，而且比较有趣的一件事情是这个定理也可以推广到期望上。

因为\(|n-k| \leq 10\)，所以我们把求第\(k\)小改为第\(k\)大，那么就有\(k \leq 11\)。

那么我们就只需要支持快速的求出所有满足\(|T| \geq k\)的\(S\)的子集的贡献。这个显然不能直接枚举，考虑DP。

设\(f_{i,j,k}\)表示考虑了前\(i\)个物品，\(\sum\limits_{T \subseteq [1,i] , \sum\limits_{x \in T} p_x = j} (-1)^{|T| - k} \binom{|T| - 1}{k - 1}\)的值。转移有两种情况：

1、第\(i\)个物品不选，从\(f_{i-1,j,k}\)转移；

2、选择第\(i\)个物品，那么

\(\begin{align*}f_{i,j,k} += & \sum\limits_{T \subseteq [1,i-1] , \sum\limits_{x \in T} p_x = j - p_i} (-1)^{|T|+1-k} \binom{|T|}{k-1} \\ = & \sum\limits_{T \subseteq [1,i-1] , \sum\limits_{x \in T} p_x = j - p_i} (-1)^{|T|+1-k} (\binom{|T| - 1}{k - 1} + \binom{|T - 1|}{k - 2}) \\ = & -\sum\limits_{T \subseteq [1,i-1] , \sum\limits_{x \in T} p_x = j - p_i} (-1)^{|T| - k} \binom{|T| - 1}{k - 1} + \sum\limits_{T \subseteq [1,i-1] , \sum\limits_{x \in T} p_x = j - p_i} (-1)^{|T| - (k - 1)} \binom{|T| - 1}{k - 2} \\ =& f_{i-1,j-p_i,k-1} - f_{i-1,j-p_i,k} \end{align*}\)

所以\(f_{i,j,k} = f_{i-1,j,k} + f_{i-1,j-p_i,k-1} - f_{i-1,j-p_i,k}\)

值得注意的是初值。当\(j=0\)或者\(k=0\)的时候应该所有的dp值都是\(0\)，但是注意到转移\(f_{i,p_i,1}\)的时候，我们可以在空集中加入\(i\)号元素产生\(1\)的贡献，也就是说\(f_{x,0,0} (x \in [0 , N]) =1\)，其他的都是\(0\)。

最后枚举集合\(T\)的元素和就可以求出答案了。

#include<bits/stdc++.h>

//this code is written by Itst

using namespace std;

#define int long long

const int MOD = 998244353;

int dp[2][10003][15] , N , M , K , p[1003] , inv[10003];

signed main(){

#ifndef ONLINE_JUDGE

    freopen("in","r",stdin);

    //freopen("out","w",stdout);

#endif

    cin >> N >> K >> M; K = N - K + 1;

    dp[0][0][0] = 1; int now = 0;

    for(int i = 1 ; i <= N ; ++i){

        cin >> p[i];

        now ^= 1; memset(dp[now] , 0 , sizeof(dp[0]));

        dp[now][0][0] = 1;

        for(int j = 1 ; j <= M ; ++j)

            for(int k = 1 ; k <= K ; ++k)

                dp[now][j][k] = (dp[now ^ 1][j][k] + (j >= p[i] ? dp[now ^ 1][j - p[i]][k - 1] - dp[now ^ 1][j - p[i]][k] + MOD : 0)) % MOD;

    }

    inv[1] = 1;

    for(int i = 2 ; i <= M ; ++i) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;

    int ans = 0;

    for(int i = 1 ; i <= M ; ++i) ans = (ans + dp[now][i][K] * inv[i]) % MOD;

    cout << ans * M % MOD;

    return 0;

}

巴特西

Luogu4707 重返现世 min-max容斥、DP

最新文章

热门文章