​

容斥原理

设S是一个有限集，A_1,A_2…A_n是S的n个子集，则

$|S-{\bigcup }_{i=1}^n{A}_i|={\sum }_{i=0}^n(-1{)}^i{\sum }_{1\le j_1<j_2...<j_i\le n}|{\bigcap }_{k=1}^i{A}_{j_k}|$

基本应用：

m件不同的物品，分给n个人，要求每一个人至少分得一件物品，求不同的分配方案数

令$A_i$表示第i个人没有物品，$S$表示$m$个物品分给$n$个人的总方案数

则$|S-{\bigcup }_{i=1}^n{A}_i|={\sum }_{i=0}^n(-1{)}^i{\sum }_{1\le j_1<j_2...<j_i\le n}|{\bigcap }_{k=1}^i{A}_{j_k}|$

$={\sum }_{i=0}^n(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})(n-i{)}^m$

有 $2n$个元素 $a_1,a_2,...,a_n$ 和$b_1,b_2,...,b_n$，求有多少个它们的全排列，满足任意的

$1\le i\le n$,$a_i$ 和$b_i$ 都不相邻。

同样的，令$A_i$表示$a_i$和$b_i$相邻，

则$|S-{\bigcup }_{i=1}^n{A}_i|={\sum }_{i=0}^n(-1{)}^i{\sum }_{1\le j_1<j_2...j_i\le n}|{\bigcap }_{k=1}^i{A}_{j_k}|$
$={\sum }_{i=0}^n(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})|有i对相邻的方案数|$
$={\sum }_{i=0}^n(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})2^i\ast (2n-i)!$

有了以上基本常识就可以上大招了

例题

CF449D

大意：
给出一个长度为n的序列$a_1,a_2...a_n$。求从中选择一个非空子集使得他们的按位与之和等于0的方案数

思路：
不考虑复杂度的话我们有一个非常套路的容斥做法。考虑性质Ai表示子集与之后第i位为1，那么我们的答案其实就是
$|\Omega -A_1\bigcup A_2...\bigcup A_{20}|={\sum }_{i=0}^{20}(-1{)}^i{\sum }_{1\le j_1<j_2...<j_i\le 20}|A_{j_1}\bigcup A_{j_2}...A_{j_i}|$
其中||符号就表示集合的大小

显然就可以状压枚举，这样的时间复杂度是$O(n\ast 1e6)$，考虑优化。

注意到对于$|A_{j_1}\bigcup A_{j_2}...A_{j_i}|$，我们记满足对应所有性质的元素的个数为k，则该集合的大小就是$2^k-1$,那么什么元素会满足这些性质呢？就是二进制为其超集的元素呗，其价值就是1.

所以我们只要做一遍超集后缀和即可，时间复杂度来到$O(20\ast 1e6)$

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll N=1e5+10;
const ll mod=1e9+7;
ll n,cnt=0,a;
ll mas[N];
ll up=20;
ll vis[30];
ll dp[(1<<20)+10];
ll ksm(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1) ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
ll gt()
{
    ll tot=0;
    ll fl;
    for(int i=1;i<=n;++i)
    {
        fl=1;
        for(int j=0;j<up;++j)
        {
            if(!vis[j]) continue;
            if((mas[i]&(1<<j))==0)
            {
                fl=0;
                break;
            }
        }
        if(fl) tot++;
    }

    return ((ksm(2,tot)-1)%mod+mod)%mod;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a,dp[a]++;
    for(int j=0;j<up;++j)
    {
        for(int i=0;i<(1<<up);++i)
        {
            if((i&(1<<j))==0) dp[i]+=dp[i^(1<<j)];
        }
    }
    ll ans=0;
    for(int s=0;s<(1<<up);++s)
    {
        cnt=0;
        for(int i=0;i<up;++i) if(s&(1<<i)) cnt++;
        if(cnt%2) ans=((ans-ksm(2,dp[s])+1)%mod+mod)%mod;
        else ans=((ans+ksm(2,dp[s])-1)%mod+mod)%mod;
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

CF1799G

大意：

思路：
个人认为这道题还是很顶的

题目有两个限制：每个人要得到$c_i$票，每个人不能投给自己组

然后这里就有一个很巧妙的转化：我们可以先将同一个组的人放在一起来看，这样就可以将第一个限制稍微弱化一些，最后我们再想办法处理组内的方案数

那么此时的问题如下：每一个组$i$总共有$nu{m}_i$人,总共需要$f_i$票，组内的人不能投给自己组，求合法方案数

考虑生成函数处理

我们用$a_i$来表示第$i$组的变元。那么对于第$i$组的每一个人来说，它能投给除了自己组外的任河组，所以它的贡献是$a_1+a_2+...+a_{i-1}+a_{i+1}+...+a_n$,我们可以简单记为$s-a_i$,其中s就表示${\sum }_{i=1}^n{a}_i$

那么我们最后得到式子为$(s-a_1{)}^{nu{m}_1}(s-a_2{)}^{nu{m}_2}...(s-a_n{)}^{nu{m}_n}$,记为$S$,而我们的答案显然就是$[a_1^{f_1}{a}_2^{f_2}...a_n^{f_n}](S)$.此时不难发现，对于$a_i$的指数，每一个s都可以提供1，而$(s-a_i{)}^{nu{m}_i}$中的$-a_i$也可以提供不多于$nu{m}_i$的指数。

所以我们考虑每一个$a_i$的次数${\det }_i(de{t}_i\le nu{m}_i,de{t}_i\le f_i)$,则每一个i有一个从$nu{m}_i$中选择$de{t}_i$的方案数$\left(\genfrac{}{}{0ex}{}{nu{m}_i}{de{t}_i}\right)$,并且$de{t}_i$会提供$(-1{)}^{de{t}_i}$的系数，然后剩下的所有指数都由$s$提供，总共是$\sum f_i-\sum de{t}_i=n-\sum de{t}_i$,要分成若干堆，第i堆有$f_i-de{t}_i$个，所以其实是一个可重集，不同组之间是相乘的关系，那么最终的答案其实就是
$$ans=\sum _{de{t}_i\le f_i}(-1{)}^{\sum de{t}_i}\prod (\left(\genfrac{}{}{0ex}{}{nu{m}_i}{de{t}_i}\right))(\genfrac{}{}{0ex}{}{(n-\sum de{t}_i)!}{(f_1-de{t}_1)!(f_2-de{t}_2)!...(f_n-de{t}_n)!})$$
$$=\prod nu{m}_i\ast \sum _{de{t}_i\le f_i}(-1{)}^{\sum de{t}_i}\frac{(n-\sum de{t}_i)!}{\prod de{t}_i!(nu{m}_i-de{t}_i)!(f_i-de{t}_i)!}$$

那么其实n只有200，所以我们可以比较轻松地来得到这个式子的结果

考虑枚举$\sum de{t}_i$,我们记为$d$,那么再记一个$d{p}_{i,j}$表示当前处理到了第i组，${\sum }_{x\le i}de{t}_i=j$,显然只要在过程中枚举合法的$de{t}_i$就能完成这个dp了，外层枚举d，内层枚举i,j,最内层枚举$de{t}_i$,乍一看时间复杂度好像是$O(n^4)$,但是因为$de{t}_i\le nu{m}_i$,而$\sum nu{m}_i=n$,所以实际复杂度只有$O(n^3)$

这样我们就完成了组与组之间的关系。考虑组内部的票数分配，$nu{m}_i$个人，每一个人需要$c_i$票，总共$\sum c_i=f_i$票，所以这其实还是一个多重集，那么我们只要乘上系数$\frac{f_i!}{\prod c_i!}$即可

推推式子还是有点累的~

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll N=210;
const ll mod=998244353;
ll n;
ll f[N],t[N],c[N],num[N];//每一组的总期望票数，组别，个人期望票数,每组人数
ll dp[N][N];
ll ksm(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1) ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
ll inv(ll x)
{
    return ksm(x,mod-2);
}
ll p[N],pp[N];
void init(ll n)
{
    p[0]=1;
    for(ll i=1;i<=n;++i) p[i]=p[i-1]*i%mod;
    pp[n]=inv(p[n]);
    for(int i=n-1;i>=0;--i) pp[i]=pp[i+1]*(i+1)%mod;

}
void solve()
{
    init(200);
    // for(int i=1;i<=10;++i) cout<<p[i]<<" "<<pp[i]<<endl;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>c[i];//期望票数
    for(int i=1;i<=n;++i) cin>>t[i],f[t[i]]+=c[i];
    for(int i=1;i<=n;++i) num[t[i]]++;
    ll ans=1,sum=0;
    for(int i=1;i<=n;++i) ans=ans*p[num[i]]%mod;
    
    for(int d=0;d<=n;++d)//det_i之和
    {
        for(int i=1;i<=n;++i) for(int j=0;j<=n;++j) dp[i][j]=0;
        dp[0][0]=p[n-d];

        for(int i=1;i<=n;++i)
        {
            //当前枚举到第i组
            for(int j=0;j<=d;++j)//到第i个人位置det_i的总和为j
            {
                for(int k=0;k<=min(f[i],num[i])&&k<=j;++k)//det_i=k
                {
                    ll det=pp[k]*pp[num[i]-k]%mod*pp[f[i]-k]%mod;
                    dp[i][j]=(dp[i][j]+det*dp[i-1][j-k]%mod)%mod;
                }
            }
        }
        if((d%2)==0) sum=(sum+ans*dp[n][d]%mod)%mod;
        else sum=((sum-ans*dp[n][d]%mod)%mod+mod)%mod;
    }
    for(int i=1;i<=n;++i)//组内多重集
    {
        sum=sum*p[f[i]]%mod*pp[c[i]]%mod;
    }
    cout<<sum<<endl;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

未完待续

​