两种常用形式

第一种 由“至少”到“恰好”

$f(k)$表示至少满足$k$个条件的方案数

$g(k)$表示恰好满足$k$个条件的方案数

则 组合容斥形式$$f(k)=\sum\limits^{n}_{i=k}C^{k}_{i}g(i)$$$$g(k)=\sum\limits^{n}_{i=k}(-1)^{i-k}C^{k}_{i}f(i)$$

集合形式$$f_S=\sum\limits_{S\subseteq S'}g_{S'}$$$$g_S=\sum\limits_{S\subseteq S'}(-1)^{|S'|-|S|}f_{S'}$$

可以发现$\sum$的下标一样 可以知上求下

比如这道题

$P4859$ 已经没有什么好害怕的了

要求恰好有$\frac{n+k}{2}$个$a_i>b_i$的 转化为至少有几个 用$Dp$可以在排序后求出 然后直接套式子即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=2019;
const int p=1e9+9;
int n,k,a[maxn],b[maxn],dp[maxn][maxn],l[maxn],fact[maxn],C[maxn][maxn];

int f(int x)//至少满足x个条件的方案数 
{
    return 1ll*dp[n][x]%p*fact[n-x]%p;
}

int main()
{
    scanf("%d%d",&n,&k);
    if((n+k)&1){puts("0");return 0;}k=(n+k)/2;//a[i]>b[i]的需要恰好k=(n+k)/2个
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    fact[0]=1;
    for(int i=1;i<=n;i++)fact[i]=1ll*fact[i-1]%p*i%p;
    C[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++)
            C[i][j]=(C[i-1][j]+(j>=1?C[i-1][j-1]:0))%p;
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    int now=0;
    for(int i=1;i<=n;i++){
        while(now<n&&b[now+1]<a[i])++now;
        l[i]=now;
    }
    dp[1][0]=dp[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++)//l[i]为比它小的数的个数 
            dp[i][j]=(dp[i-1][j]+(j>=1?1ll*(l[i]-(j-1))%p*dp[i-1][j-1]%p:0))%p;
    int ans=0;
    for(int i=k;i<=n;i++)//由至少到恰好 
        ans=(ans+1ll*(long long)pow(-1,i-k)*C[i][k]%p*f(i)%p)%p;
    cout<<ans;
}

第二种 由“至多”到“恰好”

$f(n)$表示至多满足$n$个条件的方案数

$g(n)$表示恰好满足$n$个条件的方案数

$$f(n)=\sum\limits^{n}_{i=0}C^i_ng(i)$$

$$g(n)=\sum\limits^n_{i=0}(-1)^{n-i}C^i_nf(i)$$

集合形式$$f_S=\sum\limits_{S'\subseteq S}g_{S'}$$$$g_S=\sum\limits_{S'\subseteq S}(-1)^{|S|-|S'|}f_{S'}$$ 可以发现$\sum$的下标一样 可以知上求下

数论中的莫比乌斯反演和组合中的容斥原理，皆是偏序集上 容斥原理的特殊情景。