min-max容斥

· · 个人记录

经典形式

结论很简单，对于一个集合S，令max(S),min(S)为其中的最大（小）元素，则有

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

证明也很容易，不妨假设最值唯一，考虑\max(S)只会在T恰好只有1个元素且为\max(S)时统计一次，而对于不是\max(S)的数，它在T中做最小值的出现次数一定是偶数次，而且一定可以两两抵消，所以最后就只剩\max(S)，原式成立

例题:[HAOI2015]按位或

因为期望是线性的，所以上述结论在期望下也成立

令E[\max(S)]表示S中最迟元素出现时间的期望，min同理

那么答案就是E[\max(U)]

考虑怎么求E[\min(S)]，即最早元素的出现时间，也就是随便出现个元素就行，即E[\min(S)]=\frac{1}{\sum_{i\&S\neq \varnothing}p_i}，而有交集可以变成求没有交集的，所有与S没有交集的集合就是U^S的子集，也就是需要对一个集合的子集求和，对这个序列DWT一次即可

#include<bits/stdc++.h>
#define N (1 << 20) + 5
#define ld double
using namespace std;
int n,cnt[N];
ld p[N];
int main()
{
    scanf("%d",&n); n = (1 << n);
    for(int i=0;i<n;++i) scanf("%lf",p + i),cnt[i] = cnt[i >> 1] + (i & 1);
    for(int i=1;i<n;i<<=1)
      for(int j=0;j<n;j+=(i<<1))
        for(int k=0;k<i;++k)
          p[j + k + i] += p[j + k];
    ld ans = 0; int s = (n - 1);
    for(int i=1;i<n;++i) if(1 - p[s ^ i] > 1e-8) ans += ((cnt[i] & 1) ? 1 : -1) / (1 - p[s ^ i]);

    if(ans < 1e-10) puts("INF");
    else printf("%.10lf\n",ans);
    return 0;
}

扩展min-max容斥

将上面的最大变成第k大：

\max_k(S)=\sum_{T\subset S} \binom{|T| - 1}{k - 1}(-1)^{|T| - k}\min(T)

在期望下同理,证明不会（列个式子二项式反演？）

例题：重返现世

求的是\min_k(U)，令k=n+1-k，那么就是求\max_k(U),k\leq 11，可以套上面的式子，其中\min(T) = \frac{m}{\sum_{i\in T}p_i}

枚举子集T显然不现实，可以发现影响答案的变量有：\sum_{i\in T}p_i和|T|，两者的上界分别是m和n，考虑以此DP

令f_{i,j}表示考虑了前i个原料，\min(T)=\sum_{i\in T}p_i=j时的\sum_{T\subset S}\binom{|T| - 1}{k - 1}(-1)^{|T| - k}（将上面的式子一部分拆成状态，一部分拆成值）

考虑加入一个原料i，如果它不选它，会从f_{i-1,j}转移过来

如果选它，考虑贡献是多少：在没有它的所有集合|T|中加入i，集合大小+1，即贡献为\sum_{T\subset S}\binom{|T|}{k-1}(-1)^{|T| -k + 1}

将组合数拆开可以得到

\sum_{T\subset S}\binom{|T|-1}{(k-1)-1}(-1)^{|T| - (k - 1)}-\sum_{T\subset S}\binom{|T| - 1}{k}(-1)^{|T|-k}

搞到这里发现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}，时空复杂度均为O(nmk)，需要滚掉i这一维

#include<bits/stdc++.h>
#define N 1005
using namespace std;
typedef long long ll;
const ll mod = 998244353;
int n,mx,m,now = 1,las = 0;
ll p[N],f[2][N*10][12];
ll qp(ll a,ll b) { ll ret=1; for(;b;b>>=1,a=a*a%mod) if(b & 1) ret=ret*a%mod; return ret; }

int main()
{
    cin>>n>>mx>>m;
    mx = n + 1 - mx;
    for(int i=1;i<=n;++i) cin>>p[i];
    for(int i=1;i<=n;++i)
    {
        swap(now,las);
        for(int j=1;j<=m;++j)
        {
            for(int k=1;k<=mx;++k)
            {
                f[now][j][k] = 0;
                if(j < p[i]) f[now][j][k] = f[las][j][k];
                if(j == p[i]) f[now][j][k] = (f[las][j][k] + (k == 1));
                if(j > p[i]) f[now][j][k] = (f[las][j][k] + f[las][j - p[i]][k - 1] - f[las][j - p[i]][k]) % mod;
            }
        }
    }
    ll ans = 0;
    for(int i=1;i<=m;++i) ans = (ans + m * qp(i,mod - 2) % mod * f[now][i][mx] % mod) % mod;
    cout<<(ans + mod) % mod<<endl;
    return 0;
}