学习心得 - 数学 - Min-Max 容斥【洛谷 P4707】

· · 算法·理论

续集。

形如如下的式子：

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

同理：

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

我不会证，但是我会用举例：我们都知道下列式子成立：

\max(a,b)=a+b-\min(a,b)

同理，可以合并：

\max(a,b,c)=a+b+c-\min(a,b)-\min(b,c)-\min(a,c)+\min(a,b,c)

以此类推，我们可以推广到任意长度的 S 集合。

Min-Max 容斥可以推广到任何有关 Min-Max 的东西，比如 \gcd，\operatorname{lcm}（本质是指数上的 Min-Max）还有 kth 的 Min-Max，比较复杂，以及位运算 \operatorname{and}，\operatorname{or} 是位 Min-Max。

扩展 \min-\max 容斥【P4707 重返现世】

式子增加一个组合式子，如下：

\max_k(S)=\sum_{T\subseteq S,T\neq \varnothing} (-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)

例题就拿 P4707 吧，题目大意：有 n 种材料，你需要其中任意 k 种，每一个都有一个概率出现。问收集到 k 种的期望时间。

首先我们 Min-Max 容斥都存在的共性是可期望性。怎么建模成集合？考虑最终的集合 S，显然期望时间就是 E(\min_k(S))，也就是只看种类，第 k 小的时间。显然我们不好看这个，那么就转化为 E(\max_k(S))，即 n-k+1\to k。

然后 n\le 1000，显然不能所有集合 T 都求一遍答案。但是 \color{red}n-k+1\le 10（题目特殊条件），考虑如何利用这个。目前我们转化后，显然就有 k\le 10。那么我们就可以使用 \mathcal O(nmk) 的 DP？卡卡空间试试。

首先我们设 f_{i,j,k} 为前 i 种材料，选择了其中 j 种，然后目前期望值为 k 的 \min(T) 系数（显然 \min(T)=k），也就是 =\sum_{T\subseteq S,T\neq \varnothing} (-1)^{|T|-k}\binom{|T|-1}{k-1}。答案是容易的，我们考虑转移：

  1. 不选择第 i 种状态：啥都不会影响（甚至连期望值都没有！）。
  2. 选择：会影响 |T|-k 的值和 \binom{|T|-1}{k-1}。首先 |T|-k 直接正负性更改，然后后面这一项就考虑本质：\binom{|T|}{k-1}=\binom{|T|-1}{k-1}+\binom{|T|-1}{k-2}，考虑这两个所属的子状态，拆分一下可以得到：f_{i,j,k}=f_{i-1,j-1,k-p_i}-f_{i-1,j,k-p_i}。

然后最后一个问题：f_{0,j,0} 的初始化。如何保证 |T|=k 贡献为 1？就可以用 f_{0,0,0}=0，此时不会有影响，其余都赋值成 -1。考虑 -f_{i-1,j,k-p_i}，此时我们不能让 f_{0,0,0} 有 f_{i-1,j-1,k-p_i} 的贡献，但是如果其他都是 -1，此时就可以存在 1 的贡献，就可以计算出来了。

空间压掉无关紧要的 i 即可。代码回来写。

// #define File
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
using namespace std;
const ll inf=1e12, P=998244353;
const int N=1e3+10, M=1e4+10;
ll qp(ll a,ll b){
    ll res=1;
    for(;b;b>>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;
    return res;
}
ll f[15][M];
int n,m,kl,p[N];
void solve(){
    cin>>n>>kl>>m;
    kl=n-kl+1;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int j=1;j<=kl;j++) f[j][0]=-1;
    for(int i=1;i<=n;i++) for(int j=kl;j>=1;j--)
        for(int k=m;k>=p[i];k--) f[j][k]=(f[j][k]+((f[j-1][k-p[i]]-f[j][k-p[i]])%P+P)%P)%P;
    ll ans=0;
    for(int i=1;i<=m;i++)
        ans=(ans+f[kl][i]*qp(i,P-2)%P)%P;
    cout<<ans*m%P;
    return;
}
int main(){
    #ifdef File
        freopen("readfile.in","r",stdin);
        freopen("readfile.out","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=1; // cin>>T;
    while(T--) solve();
    return 0;
}