容斥原理，多步容斥

1. 容斥意义法
   设计状态表示容斥的过程。比较简单的容斥题目一般可以容斥意义。
   如果我们要求方案数的话，通常情况下我们的把限制视为两个方面，一方面是总限制，一方面是对于每个物品的限制，这样设集合$S_i$表示满足总限制以及对第$i$个限制的方案构成的集合，若答案为$\left|\underset{i=1}{\bigcup ^n}{S}_i\right|$或$\left|\underset{i=1}{\bigcap ^n}{S}_i\right|$，则可以使用容斥原理求解。
2. 容斥符号法
   如果认为这个题是容斥，并且没什么太好的容斥想法，可以尝试容斥符号，例如把$=$为$\le$或$\ge$，$=$为$\subseteq ,\supseteq$（例如把双射容斥为子集），$\subset$为$\subseteq$
3. 修正法
   可以先编一个错误的答案，然后再考虑如何容斥掉多余的部分。很多较为复杂的题都可以修正。

容斥原理

一般的容斥原理就是设出集合，使得集合的并/交为答案，然后利用容斥原理求解的过程。
如果设不出集合，或者难以求解，则可以考虑更加复杂的计数方式，例如反演。

容斥原理：
$补集转换:S=U-\overline{S}$
$德\cdot 摩根定律:\overline{\underset{i=1}{\bigcup ^n}{S}_i}=\underset{i=1}{\bigcap ^n}\overline{S_i},\overline{\underset{i=1}{\bigcap ^n}{S}_i}=\underset{i=1}{\bigcup ^n}\overline{S_i}$
$集合的并:\left|\underset{i=1}{\bigcup ^n}{S}_i\right|=\sum _{\varnothing \ne T\subseteq [n]}(-1{)}^{|T|-1}\left|\bigcap _{i\in T}{S}_i\right|$
$集合的交:\left|\underset{i=1}{\bigcap ^n}{S}_i\right|=\sum _{T\subseteq [n]}(-1{)}^{|T|}\left|\bigcap _{i\in T}\overline{S_i}\right|$

事实上求解集合的交的式子是由两步构成，根据德·摩根定律，$\left|\underset{i=1}{\bigcap ^n}{S}_i\right|=U-\left|\underset{i=1}{\bigcup ^n}\overline{S_i}\right|$
这说明集合的交=全集-补集的并，但是并集往往都比交集更难求解（除非集合之间没有交时，并集才好求解，但是我们在求解补集的并时，如果各个补集之间没有交，说明原集的并为全集，这样就不用求解了），因此我们注意到$\left|\underset{i=1}{\bigcup ^n}\overline{S_i}\right|$也是集合的交集的形式，因此我们套用容斥原理进行求解，这样的过程叫做有人称为多步容斥。

补集转化

补集转化较简单。

有标号连通图计数

求$n$个节点的无向连通图有多少个，节点有标号，编号为 $[1,n]$
$n<=5000$

这个题是朴素容斥，即考虑如何用容斥原理来修正答案。

设$f_i$表示大小为$i$的连通图数量，一个想法是首先连出一棵树，但是不太好搞，考虑补集转换，总边数为$\frac{i(i-1)}{2}$，总可能性为$h(i)=2^{\frac{i(i-1)}{2}}$种，减去不连通的情况即可，那我们枚举$1$号点所在的连通块大小$j$，然后从剩下的$i-1$个点中选出$j-1$个点，情况数量为：$f_j\left(\begin{array}{c}i-1\\ j-1\end{array}\right)$，剩下$i-j$个点随意连边，转移方程为：
$f_i=h(i)-\sum _{j<i}{f}_j\left(\begin{array}{c}i-1\\ j-1\end{array}\right)h(i-j)$

集合的交

容斥原理求解集合的交比较多，求解并反而比较少，因为题目往往要求同时遵守所有限制，而不是只遵守其中一个，这符合交的形式。

CF451E

限制$f_i$是难以求解的，去掉$f_i$的限制是好做的，很容易想到把它容斥掉。

容斥意义法：我们把选择$s$朵花看做总限制，对第$i$个花瓶的限制设出集合，则$S_i$表示满足总共选了$s$朵花，并且第$i$个花瓶的花$\le f_i$的方案的集合，则答案为$\left|\underset{i=1}{\bigcap ^n}{S}_i\right|$，容易想到用容斥原理来求解。
则：$\left|\underset{i=1}{\bigcap ^n}{S}_i\right|=\sum _{T\subseteq [n]}(-1{)}^{|T|}\left|\bigcap _{i\in T}\overline{S_i}\right|$，对于$T$，我们要求出限制$i\in T$均不合法的方案数，则我们指定物品$i$至少选择了$f_i+1$次，剩下的次数为$s-\sum _{i\in T}(f_i+1)$，我们将它们划分到$n$个花瓶中，根据集合的定义，我们不需要管这些花瓶的限制，这是隔板法问题，即$\left(\begin{array}{c}s-\sum _{i\in T}(f_i+1)+n-1\\ n-1\end{array}\right)$。因此最终的式子就是：$\left|\underset{i=1}{\bigcap ^n}{S}_i\right|=\sum _{T\subseteq [n]}(-1{)}^{|T|}\left(\begin{array}{c}s-\sum _{i\in T}(f_i+1)+n-1\\ n-1\end{array}\right)$

注：部分题解当中提到了“多重集的组合数”，很容易看成是“多重组合数”，但其实两者没啥关系。

代码（值域很大的组合数很难直接求解，我们把组合数转化为下降幂求解）：

#include<iostream>
using namespace std;
const int N=20;
const long long M=1e9+7;
long long pow(long long a,long long b,long long c) {long long ans=1;while(b) {if(b&1) (ans=ans*a)%=M;(a=a*a)%=M;b>>=1;}return ans;
}
long long inv(long long x) {return pow(x,M-2,M);
}
long long a[N+5];
int n;
long long m;
long long d(long long x,long long k) {if(k==0) return 1;else return x%M*d(x-1,k-1)%M;
} 
long long calc(int s) {long long sum=0;for(int i=1;i<=n;i++) if(s>>i-1&1) sum+=a[i]+1;if(m-sum<0) return 0;return d(m-sum+n-1,n-1)*inv(d(n-1,n-1))%M;
} 
int main() {cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];long long ans=0;for(int s=0;s<1<<n;s++) (ans+=calc(s)*(__builtin_popcount(s)&1?-1:1))%=M;cout<<(ans%M+M)%M;
}

P1450

容易想到把$d_i$容斥掉。

容斥意义：我们把购买了价值为$s$的物品作为总限制，把对硬币$i$的数量的限制作为集合，则设$S_i$表示满足对第$i$个硬币数量限制，且购买了价值为$s$的物品的方案的集合，则答案为$\left|\underset{i=1}{\bigcap ^4}{S}_i\right|$，接下来根据$\left|\underset{i=1}{\bigcap ^n}{S}_i\right|=\sum _{T\subseteq [n]}(-1{)}^{|T|}\left|\bigcap _{i\in T}\overline{S_i}\right|$，我们要求解补集的交，即对于一些硬币的限制不满足的方案数。
如果硬币$i\in T$的限制不满足，显然它选了至少$d_i+1$个，我们提前dp出$f_x$表示购买了价值为$s$物品的完全背包方案数，则此时的方案数量为$f_{s-\sum _{i\in T}(d_i+1)}$。

则本次询问的答案为：$\left|\underset{i=1}{\bigcap ^4}{S}_i\right|=\sum _{T\subseteq [4]}(-1{)}^{|T|}{f}_{s-\sum _{i\in T}(d_i+1)}$

每做一次询问，我们就进行一次容斥，复杂度为$O(2^4)$，因此总复杂度为$(n\cdot 2^4)$

#include<iostream>
#include<algorithm>
using namespace std;
const int R=100000;
long long f[R+5];
int a[10],b[10];
long long calc(int s,int x) {int t=1;while(s) x-=(s&1)*a[t]*(b[t]+1),s>>=1,t++;if(x<0) return 0;else return f[x];
}
int main() {int n;cin>>a[1]>>a[2]>>a[3]>>a[4]>>n;f[0]=1;for(int i=1;i<=4;i++)for(int j=a[i];j<=R;j++) f[j]+=f[j-a[i]];while(n--) {int x;cin>>b[1]>>b[2]>>b[3]>>b[4]>>x;long long ans=0;for(int i=0;i<1<<4;i++) ans+=calc(i,x)*(__builtin_popcount(i)&1?-1:1);
//		cout<<"***";cout<<ans<<endl;}
}

UVA11806

将 k 个棋子放在 $n\times m$ 的棋盘上。我们将连续的紧贴棋盘边界的放置棋子位置称为边缘。问上下左右四个边缘上都至少放置一个棋子的棋子放置方案共有多少种.
可以做到$n\times m\le 10^5,k\le 10^5$

容斥意义：我们总共四个边缘，我们设$S_i$表示第$i$个边缘有棋子的所有方案构成的集合，则答案为$\left|\bigcap S\right|$，求解补集相当于指定一些边缘没有棋子，剩下位置随意，容斥原理求解即可。

互质问题1

给出一个整数$n$和一个整数$m$，求$[1,m]$之中有多少个数与$n$互质。
$1\le n,m\le 10^{18}$

首先我们会分析出来，如果与$n$互质，则说明这个数不含有$n$的任何一个质因子，因此可以容斥意义：设$S_i$表示$[1,m]$中不含有$n$的第$i$个本质不同质因子的数的集合，则答案为$|\bigcap S_i|$，对应的$T$相当于求出$[1,m]$之中有多少个数含有质因子集合$T$，则方案数为$\lfloor \frac{m}{\prod _{i\in T}{p}_i}\rfloor$。

这个容斥的时间复杂度为$O\left(2^{|P|}\right)$，其中$P$表示$n$的本质不同质因子构成的集合，则$|P|=O(\ln \ln n)$

互质问题2

给出一个整数$m$，一个具有$n$个元素的数组，求出$[1,m]$中有多少个数与$n$的所有元素互质：
$n\le 20,m\le 2^{62}$

首先会考虑到，与$n$中所有元素互质，相当于没有$n$中任何一个元素的任何一个质因子，因此我们可以将求出$n$中的本质不同质因子集合，设为$P$，则问题转化为求出$[1,n]$当中有多少个数与$\prod P$互质。

POJ1091

给定$n$个数，其数值取值范围为$[1,m]$，请问有多少种情况使得这$n$个数与$m$的最大公约数为$1$。
$n,m=10^5$

相当于对序列计数，满足： { a n } , a i ∈ [ 1 , m ] , gcd ⁡ ( gcd ⁡ n i = 1 { a i } , m ) = 1 \{a_n\},a_i\in[1,m],\gcd\left(\underset{i=1}{\overset n\gcd}\{a_i\},m\right)=1 {an​},ai​∈[1,m],gcd(i=1gcdn​​{ai​},m)=1

我们会发现，如果序列的$\gcd$与$m$不互质，说明它含有$m$的某些质因子，则说明序列中的每个数都含有这些质因子。因此我们可以用容斥意义来做这个题：设$S_i$表示$m$的第$i$个本质不同质因子不出现在序列最大公约数的方案的集合，则答案为$|\bigcap S_i|$，那么补集为指定$m$的质因子集合的子集$T$是序列每一个元素的约数，也就是说序列每一个数都是$\prod _{i\in T}{p}_i$的倍数，那这样的序列共有${\lfloor \frac{m}{\prod _{i\in T}{p}_i}\rfloor }^n$，容斥原理求解即可。

集合的并

HDU1796

题意简述：给出一个具有$n$个元素的数组和一个整数$m$，求出$[1,m]$中有多少个数至少能整除$a$数组中的一个数。
$n\le 10,a_i,m\le 2^{31}$

可以想到，能够整除$x$的数的数量为${\sigma }_0(x)$，能够整除$y$的数量为${\sigma }_0(y)$，还要在减去算重的数量，也就是既整除$x$又整除$y$的数，数量为${\sigma }_0(\gcd (x,y))$
其中${\sigma }_0$表示约数个数函数。

容斥意义：我们把值域为$[1,m]$作为总限制，对“能够整除$a_i$”设计集合，则$S_i$表示能够整除$a_i$的数的集合，答案为$\left|\underset{i=1}{\bigcup ^n}{S}_i\right|$，则我们根据$\left|\underset{i=1}{\bigcup ^n}{S}_i\right|=\sum _{\varnothing \ne T\subseteq [n]}(-1{)}^{|T|-1}\left|\bigcap _{i\in T}{S}_i\right|$，只需要求解集合的交即可。
也就是对于$T$来说，求出是所有能够整除$i\in T$的数的数量，也就是 σ 0 ( gcd ⁡ i ∈ T { a i } ) \sigma_0\left({\underset{i\in T}\gcd \{a_i\}}\right) σ0​(i∈Tgcd​{ai​})，因此答案为 ∣ ⋃ n i = 1 S i ∣ = ∑ ∅ ≠ T ⊆ [ n ] ( − 1 ) ∣ T ∣ − 1 σ 0 ( gcd ⁡ i ∈ T { a i } ) \left|\underset{i=1}{\overset{n}{\bigcup}}S_i \right|={\underset{\varnothing\not=T\subseteq [n]}{\overset{}\sum}}(-1)^{|T|-1}\sigma_0\left({\underset{i\in T}\gcd \{a_i\}}\right) ​i=1⋃n​​Si​ ​=∅=T⊆[n]∑​​(−1)∣T∣−1σ0​(i∈Tgcd​{ai​})
约数个数函数可以通过预处理质因子等手段求出。

时间复杂度为$O(2^n)$

P3349

这个题还可以子集反演，本质上是一样的。不过这个题完全可以直接容斥。

我们要建立一个从树节点到图节点的映射$f$，使得$f$为一个双射，这是不好限制的，我们把它转化为，$f$共有$n$个不同的像。

那我们设$S_i$表示第$i$个图节点是像的方案的集合，则答案为$\left|\underset{i=1}{\bigcap ^n}{S}_i\right|=\sum _{T\subseteq [n]}(-1{)}^{|T|}\left|\bigcap _{i\in T}\overline{S_i}\right|$，这样$T$相当于求解指定一些图节点不能使用，剩下的节点随便。

设$s=[n]\oplus T$，此时这个交集的大小是可以树形dp出来的，设$f_{u,i}$表示dp到了树节点$u$，节点$u$对应图节点$i$的方案数，则转移就是，对于$u$的儿子$v$对应的图节点为$j$，只要$(i,j)$在图上有连边，并且$i,j\in s$，就可以转移：

void dfs(int u,int fa) {for(int v=1;v<=n;v++)if(b[u][v]&&(v^fa)) {dfs(v,u);for(int i=1; i<=n; i++)if(s>>i-1&1) {long long sum=0;for(int j=1; j<=n; j++)if(s>>j-1&1)if(a[i][j])sum+=f[v][j];f[u][i]*=sum;}}
}

显然初值为$f_{u,i\in s}=1$

模拟赛题

其中$n\le 20,m\le 150,k\le 7,d\le 10^9$

这个形式看起来非常的容斥，首先考虑没有$k$的限制怎么做。这是个经典问题，设$f_{i,j}$表示第$i$秒在$j$节点的方案数，就可以写出转移，观察到$n$特别小，$d$特别大，因此可以矩阵快速幂加速转移。

那有了$k$怎么做呢？首先可以子集反演，但是容斥意义还是更简单一点的。
设$S_i$表示经过$i$节点，到了第$d$天的所有方案的集合，则答案为$|\bigcap S_i|$，补集相当于指定一些节点不能走，也就是禁止关于它们的转移，对于每个$T$跑一次dp即可。
时间复杂度$O(2^k\cdot n^3)$

后记

于是皆大欢喜。