题解 CF1400G 【Mercenaries】

· · 题解

upd on 2021.7.21：修了个 typo

先祭一个，div2 打过的最高纪录（要是我拿小号打就是 official rk 3）

我现场竟然 A 了这道题，incredible！

洛谷题面传送门 & Codeforces 题面传送门

楼下的大佬用了一种类似于图论的做法，然鹅我不会/kk，wtcl

注意到 m 的数据范围非常小，所以我们不妨用容斥原理解决这个这个问题。

通俗地讲，就是拿总方案数减去有限制不满足的情况就是答案。而计算不合法的情况，可以把有1条限制不满足的方案数加起来。但是这样会算重，故还要扣掉2条限制不满足的方案数，这样会导致3条限制不满足的情况被多减了一遍，以此类推。

具体地讲，假设所有限制组成的集合为 S，那么总方案数的表达式就是：

ans=\sum_{T \subseteq S}(-1)^{|T|}\times cnt(T)

其中 cnt(T) 表示集合 T 里的限制都不满足的情况数。

这样子枚举是 \mathcal O(2^m) 的，故接下来我们的任务就是计算 cnt(T)。

先从简单情况入手——计算总方案数，即，不考虑限制的情况下的方案数。我们枚举选中的集合的大小 x，那么 l_i \leq x \leq r_i 的 i 都可以选入集合。我们有假设 s_x 个符合条件的数，那么，用组合数可以计算得，这种情况对答案的贡献为 \dbinom{s_x}{x}。

接下来再考虑加上限制的情况，很明显，与这些限制相关的元素必须都被选中，假设有 c 个这样的元素。我们还是枚举选中的集合的大小 x，由于这 c 个元素无论如何都是要选中的，故 x 必须属于这 c 个区间的交集，设其为 [L,R]。由于 s_x 个可选的数中有 c 个已经确定下来了，故这一部分对答案的贡献为 \dbinom{s_x-c}{x-c}。

这样我们就有 cnt(T)=\sum\limits_{x=L}^R\dbinom{s_x-c}{x-c}

暴力计算肯定会 T，不过注意到 c \in [0,2m]，故可以对每个 c 都计算跑前缀和，这样可以 \mathcal O(1) 计算出答案。

然后用上面的表达式计算出答案就可以了。

怎样计算 s_x，最好的方法当然是差分。不过线段树、BIT 亦可。

#include <bits/stdc++.h>
using namespace std;
#define fi          first
#define se          second
#define pb          push_back
#define fz(i,a,b)   for(int i=a;i<=b;i++)
#define fd(i,a,b)   for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a)      a.begin(),a.end()
#define fill0(a)    memset(a,0,sizeof(a))
#define fill1(a)    memset(a,-1,sizeof(a))
#define fillbig(a)  memset(a,0x3f,sizeof(a))
#define y1          y1010101010101
#define y0          y0101010101010
#define int long long
typedef pair<int,int> pii;
inline int read(){
    int x=0,neg=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-') neg=-1;
        c=getchar();
    }
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x*neg;
}
int n=read(),m=read();
int cf[300005],l[300005],r[300005],cnt[300005],a[25],b[25];
const int MOD=998244353;
int fac[300005],inv[300005];
int qpow(int x,int e){
    int ans=1;while(e){if(e&1) ans=ans*x%MOD;x=x*x%MOD;e>>=1;} return ans;
}
inline void prework(){
    fac[0]=1;for(int i=1;i<=300000;i++) fac[i]=fac[i-1]*i%MOD;
    for(int i=0;i<=300000;i++) inv[i]=qpow(fac[i],MOD-2);
}
int sum[300005][45];
inline int getc(int x,int y){
    if(x<y||x<0||y<0) return 0;
    return fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}
signed main(){
    prework();
    fz(i,1,n){
        l[i]=read(),r[i]=read();
        cf[l[i]]++;cf[r[i]+1]--;
    }
    int num=0;
    fz(i,1,n){num+=cf[i];cnt[i]=num;}
    fz(i,1,m) a[i]=read(),b[i]=read();
    fz(i,0,40){
        fz(j,1,n){
            sum[j][i]=(sum[j-1][i]+getc(cnt[j]-i,j-i))%MOD;
        }
    }
//  cout<<sum[3][1]<<" "<<sum[1][1]<<endl;
    int ans=0;
    for(int i=0;i<(1<<m);i++){
        int _l=1,_r=n;
        set<int> st;
        fz(j,1,m){
            if(i>>(j-1)&1){
                _l=max(_l,l[a[j]]);_r=min(_r,r[a[j]]);st.insert(a[j]);
                _l=max(_l,l[b[j]]);_r=min(_r,r[b[j]]);st.insert(b[j]);
            }
        }
        if(_l>_r) continue;
        int calc=(sum[_r][st.size()]-sum[_l-1][st.size()]+MOD)%MOD;
        int cnt1=__builtin_popcount(i);
        if(cnt1&1) ans=(ans-calc+MOD)%MOD;
        else ans=(ans+calc)%MOD;
    }
    cout<<ans<<endl;
    return 0;
}

最后来总结一下这题为什么可以想到容斥原理：对于任意一条限制，若要满足它，有 3 种可能的情况（选 A、选 B、都不选）；而要不满足，只有 1 种情况（都选）。

故对于这类数据范围很小，而从正面计算比较困难的题目，可以想到容斥原理，用反面计算。