文章目录
- 容斥原理的引入
- 从集合的角度考虑
- 推广
- 例子
- 不被2、3、5整除的数
- 错排问题
- 求不定方程的解
- Devu和鲜花
容斥原理的引入
从一个小学奥数问题引入：
一个班级有50人
喜欢语文的人有20人
喜欢数学的人有30人
同时喜欢语文数学的人有10人。
问题：
- 两门都不喜欢的有多少人
- 至少喜欢一个的有多少人
至少喜欢一门 20+30-10=40 都不喜欢 50-40=10
再将上面的课程门数进一步扩展为3门，问题变为
一个班级有60人
喜欢A的人有20人
喜欢B的人有30人
喜欢C的人有25人
同时喜欢AB的人有10人
同时喜欢AC的人有7人
同时喜欢BC的人有8人
同时喜欢ABC的人有2人
至少喜欢一门的人：A+B+C-AB-AC—BC+ABC=20+30+25-10-7-8+2=52 有60-52=8个同学一门都不喜欢
从集合的角度考虑
将上述问题抽象用数学的形式表示
∣
A
∪
B
∣
=
∣
A
∣
+
∣
B
∣
−
∣
A
∩
B
∣
|A \cup B|=|A|+|B|-|A \cap B|
∣A∪B∣=∣A∣+∣B∣−∣A∩B∣
∣ A ∪ B ∪ C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ − ∣ A ∩ B ∣ − ∣ A ∩ C ∣ − ∣ B ∩ C ∣ + ∣ − ∣ A ∩ B ∪ C ∣ |A \cup B \cup C|=|A|+|B|+|C|-|A \cap B|-|A \cap C|-|B \cap C|+|-|A \cap B \cup C| ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣−∣A∩B∪C∣
推广
例子
不被2、3、5整除的数
890. 能被整除的数
两种实现方法
虽然说理论上dfs只有
O
(
2
n
)
O(2^n)
O(2n)的复杂度，而二进制枚举的复杂度是
O
(
m
2
n
)
O(m2^n)
O(m2n)但是实际上跑起来的效果二进制枚举跑的快很多，dfs还是跑的比较慢，可能是递归调用的开销比较大吧。
二进制枚举超集的写法
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int N=2e5+10;
void solve()
{
int n,m;cin>>n>>m;
vector<int>p(m);
rep(i,0,m-1) cin>>p[i];
int ans=0;
rep(i,1,(1<<m)-1){
int sgn=0,mul=1;
rep(j,0,m-1){
if(i&(1<<j)){
sgn++;
if(mul*p[j]>n){
mul=-1;
break;
}
mul*=p[j];
}
}
if(mul!=-1){
if(sgn&1){
//符号为正
ans+=n/mul;
}else{
ans-=n/mul;
}
}
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
dfs写法
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int N=2e5+10;
int ans=0,n,m;
vector<int>path;
vector<int>p(N);
void dfs(int u){
if(u==m){
if(!path.size()){
return;
}
int sgn=path.size()&1?1:-1;
int mul=1;
for(auto i:path){
if(mul>n){
mul=0;
break;
}
mul*=i;
}
if(mul) ans+=n/mul*sgn;
return;
}
dfs(u+1);
path.pb(p[u]);
dfs(u+1);
path.pop_back();
};
void solve()
{
cin>>n>>m;
rep(i,0,m-1) cin>>p[i];
dfs(0);
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
错排问题
错排问题：
P
i
≠
i
，
P
i
为排列
P_i \not = i，P_i为排列
Pi=i，Pi为排列
求不定方程的解
如果没有对
X
i
X_i
Xi进行限制的话，可以直接用隔板法去做，直接插入
n
−
1
n-1
n−1个隔板，答案就是
C
(
m
+
n
−
1
n
−
1
)
C(_{m+n-1}^{n-1})
C(m+n−1n−1)
但是现在对于每一个
X
i
X_i
Xi我们都有一个上限
b
i
b_i
bi
考虑容斥原理
这道题目并没有明显的容斥不像上面的倍数
我们把
0
<
=
x
i
<
=
b
i
0<=x_i<=b_i
0<=xi<=bi转化成
(
x
i
>
=
0
)
−
(
x
i
>
=
b
i
+
1
)
(x_i>=0)-(x_i>=b_i +1)
(xi>=0)−(xi>=bi+1)
(
x
i
>
=
0
)
(x_i>=0)
(xi>=0)可以理解为没有限制
(
x
i
>
=
b
i
+
1
)
(x_i>=b_i +1)
(xi>=bi+1)可以理解为最少选
b
i
+
1
b_i+1
bi+1个，做一个映射，可以用隔板法去做。
$ (^{m-b_i+1+n-1} _{n-1})$
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int N=2e5+10,mod=1e9+7;
int n,m,b[20];
int ifac,inv[20],ans;
int cal(int x){
//C(x+n-1,n-1)
//x+1,...,x+n-1/(n-1)!
int ans=1;
rep(i,1,n-1){
ans=ans*(x+i)%mod;
}
ans=ans*ifac%mod;
return ans;
}
void dfs(int d,int sgn, int sum){
if(d==n){
if(sum>m) return;
ans=(ans+sgn*cal(m-sum))%mod;
}else{
//x[i]>=0,当前这个没有违反
dfs(d+1,sgn,sum);
//x[i]>=b[i]+1，当前这个违反了
dfs(d+1,-sgn,sum+b[d]+1);
}
}
void solve()
{
cin>>n>>m;
//求n-1阶乘的逆元
ifac=1;
rep(i,1,n-1){
if(i==1) inv[i]=1;
else inv[i]=(mod-mod/i)*inv[mod%i]%mod;
ifac=ifac*inv[i]%mod;
}
rep(i,0,n-1){
cin>>b[i];
}
//第i个变量，容斥系数，数值之和
dfs(0,1,0);
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
Devu和鲜花
这个是上面的题目套了一个皮套，本质上还是不定方程的求解
dfs写法
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int N=2e5+10,mod=1e9+7;
int n,m,b[22];
int ifac,inv[22],ans;
int cal(int x){
//C(x+n-1,n-1)
//x+1,...,x+n-1/(n-1)!
int ans=1;
rep(i,1,n-1){
ans=ans%mod*(x%mod+i%mod)%mod;
}
ans=ans*ifac%mod;
return ans;
}
void dfs(int d,int sgn, int sum){
if(d==n){
if(sum>m) return;
ans+=sgn*cal(m-sum)%mod;
// ans=(ans+sgn*cal(m-sum))%mod;
}else{
//x[i]>=0,当前这个没有违反
dfs(d+1,sgn,sum);
//x[i]>=b[i]+1，当前这个违反了
dfs(d+1,-sgn,sum+b[d]+1);
}
}
void solve()
{
cin>>n>>m;
ifac=1;
rep(i,1,n-1){
if(i==1) inv[i]=1;
else inv[i]=(mod-mod/i)*inv[mod%i]%mod;
ifac=ifac*inv[i]%mod;
}
rep(i,0,n-1){
cin>>b[i];
}
//第i个变量，容斥系数，数值之和
dfs(0,1,0);
ans%=mod;
if(ans<0) ans+=mod;
cout<<ans%mod<<endl;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
