容斥原理
1. 容斥原理式子
[|S_1 cup S_2 cup S_3 cdots cup S_n| = sum_{1<i<n}|S_i| - sum_{i<i<j<m}|S_i cap S_j| + sum_{1<i<j<k<m}|S_i cap S_j cap S_k| - cdots + (-1)^{n-1}|S_i cap S_j cap S_k cap cdots cap S_n|
]
2. 一个不太严谨的证明
我们在(|S_1 cup S_2 cup S_3 cdots cup S_n|)中设一个元素为(x)，(x)在所有(S)集合中出现了(k)次((1<k<n))。则(x)在(sum_{1<i<n}|S_i|)会被加(k)次，即(C^{1}_{k})，在(sum_{i<i<j<m}|S_i cap S_j|)中会被减去(C^{2}_{k})次，以此我们可以得到以下柿子：
[C^{1}_{k} - C^{2}_{k} + C^{3}_{k} - cdots + (-1)^{k-1}C^{k}_{k}
]
由(sum^{n}_{i}C^{i}_{n})可知这个式子一定是等于(1)的，即(x)在(|S_1 cup S_2 cup S_3 cdots cup S_n|)中只会出现一次。
3. 一道简单的例题：AcWing890.能被整除的数
题比较简单，容斥+状压
#include<bits/stdc++.h>
using namespace std;
int p[1000];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>p[i];
}
int res=0;
for(int i=1;i<=(1<<m)-1;i++)
{
int t=1,cnt=0;
for(int j=0;j<m;j++)
{
if(i>>j&1)
{
cnt++;
if((long long)t*p[j+1]>n)
{
t=-1;
break;
}
t*=p[j+1];
}
}
if(t!=-1)
{
if(cnt%2) res+=n/t;
else res-=n/t;
}
}
cout<<res;
return 0;
}