01/15
21:01
OI

重返现世 [广义MinMax容斥]

重返现世

就在这里系统复习一下这类内容好了。

下面式子都是Min求Max,因为貌似用Min求Max比较多,反过来也行。

Min Max容斥:

\min(S) = \sum_{T \subseteq S} (-1)^{|T| – 1} \max(T)

广义Min Max容斥:

{\rm kthmax}(S) = \sum_{T \subseteq S} (-1)^{|T| – k} \binom{|T| – 1}{k – 1} \min(T)

只证明这个好了…

令系数为f(|T|)。钦定一个第x大的元素,考虑她对答案的贡献。容易发现和x有关的系数和是:

\sum_{i=0}^{n-x} \binom{n – x}{i} f(i+1) = [n – x = k – 1]

那么换个元

\sum_{i=0}^{m-1} \binom{m – 1}{i} f(i+1) = [m – 1 = k – 1]

二项式反演得到

f(m) = \sum_{i=0}^{m-1} \binom{m – 1}{i} [i – 1 = k – 1] (-1)^{m – k + 1}

f(m) = \binom{m – 1}{k – 1} (-1)^{m – k}


回到这题,题求的是min,k \rightarrow n – k + 1换成max

设选了一个集合,概率和为p/m,显然期望次数是m/p,于是只需要知道\sum p

设计一个反正我想不出来的神仙DP:

f_{i,j,k}表示前i个数,概率和是j,是K=k

那么有转移如下:

f_{i,j,k} = f_{i-1,j,k} + f_{i-1,j-p_i,k-1} – f_{i-1,j-p_i,k}

后面那个部分很迷惑,解释是这样的:

加了一个元素,容斥系数有一些变化。发现\binom{|T-1|}{k-1} = \binom{|T| – 2}{k – 1} + \binom{|T| – 2}{k – 2},代进去就行了。

#include <bits/stdc++.h>

const int N = 1005, M = 10005;
const int P = 998244353;

int n, K, m, p[N], f[2][M][11], now, ans;

inline void add(int &x, int y) {
  x += y;
  if (x >= P)
    x -= P;
}

inline int fpow(int x, int y) {
  int ret = 1;
  for ( ; y; y >>= 1, x = 1ll * x * x % P)
    if (y & 1) ret = 1ll * ret * x % P;
  return ret;
}

int main() {
  scanf("%d %d %d", &n, &K, &m);
  for (int i = 1; i <= n; ++i)
    scanf("%d", p + i);
  K = n - K + 1;
  f[0][0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    now ^= 1;
    for (int j = 0; j <= m; ++j)
      for (int k = 0; k <= K; ++k)
        f[now][j][k] = f[now ^ 1][j][k];
    for (int j = p[i]; j <= m; ++j)
      for (int k = 1; k <= K; ++k) {
        add(f[now][j][k], f[now ^ 1][j - p[i]][k - 1]);
        add(f[now][j][k], P - f[now ^ 1][j - p[i]][k]);
      }
  }
  for (int i = 1; i <= m; ++i)
    add(ans, 1ll * f[now][i][K] * fpow(i, P - 2) % P);
  std::cout << 1ll * ans * m % P << std::endl;
  return 0;
}