我是靠谱客的博主 潇洒月亮,这篇文章主要介绍组合计数问题中容斥原理的应用,现在分享给大家,希望可以做个参考。

容斥原理作为数学中的一个重要定理,在ACM当中也有重要的应用,可以用于解决组合计数问题,概率论问题,数论问题。

具体参见2013 成都七中 王迪 《浅析容斥原理》

容斥原理当中奇数个集合为正,偶数个集合为负。

其核心思想是:把重复的扣掉,再把扣多的加回来。

初始化时会用到的公式:

C(m,0)=C(m,m)=1      C(n,k)+C(n,k+1)=C(n+1,k+1)


1.容斥原理在组合计数当中的应用

刘汝佳《训练指南》107页的例题3   很经典的一道题目

链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2906

具体解法,参照训练指南,此处不在多论述,是一道非常经典的用二进制记录容斥原理的题目

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=500+10; const int mod=1000007; int C[maxn][maxn]; int main() { memset(C,0,sizeof(C)); //初始化 C[0][0]=1; for(int i=0;i<=500;i++) { C[i][0]=C[i][i]=1; //千万不能忘记边界条件 for(int j=1;j<i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; } int t; scanf("%d",&t); for(int cas=1;cas<=t;cas++) { int n,m,k,sum=0; scanf("%d%d%d",&n,&m,&k); for(int s=0;s<16;s++) //枚举所有16种搭配方式 { int r=n,c=m,b=0; //b用来统计集合的个数,r和c是可以放置的行列数 if(s&1) //第一行没有石头,r减1 { r--; b++; } if(s&2) //最后一行没有石头,r减1 { r--; b++; } if(s&4) //第一列没有石头,c减1 { c--; b++; } if(s&8) //最后一列没有石头,c减1 { c--; b++; } if(b&1) sum=(sum+mod-C[r*c][k])%mod; //奇数的条件,做减法(容斥原理) else sum=(sum+C[r*c][k])%mod; //偶数的条件,做加法(容斥原理) } printf("Case %d: %dn",cas,sum); } return 0; }

容斥原理的应用:

用二进制标记容斥原理,奇数的地方加,偶数的减

链接:http://acm.hdu.edu.cn/showproblem.php?pid=4336

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int maxn=20+5; double a[maxn]; int main() { int n; while(cin>>n) { for(int i=1;i<=n;i++) cin>>a[i]; double xh=0.0; for(int i=1;i<(1<<n);i++) //二进制标记容斥原理 { double sum=0.0; int odd=0; for(int j=0;j<n;j++) if((1<<j)&i) { odd++; sum+=a[j+1]; } if(odd&1) //奇数加偶数减 xh+=1.0/sum; else xh-=1.0/sum; } printf("%.6lfn",xh); } return 0; }


容斥原理在乘除问题上的应用:

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1796

求[1,r)内有因子出现在集合中的数的个数。题目要求的数要么含有一个集合中的因子,要么是两个,要么是三个..要么是m个,而含两个集合中因子的数在计算含有一个集合中的因子,被重复计算了,三个时候也在计算二个的时候被重复计算,所以需要用到容斥原理。2^m枚举集合中元素,然后计算出最小公倍数,n/LCM就是1..n中含我们枚举的因子的数的个数对于求出来的数根据枚举到素因子个数奇数加偶数加。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int maxn=20; int arr[maxn]; int n,m,cnt,ans; __int64 gcd(__int64 a,__int64 b) { if(b==0) return a; else return gcd(b,a%b); } void dfs(__int64 i,__int64 a,__int64 b) { for(;i<=m;i++) { if(arr[i]) { cnt=arr[i]*a/gcd(arr[i],a); ans+=b*(n/cnt); dfs(i+1,cnt,-b); } } return; } int main() { while(cin>>n>>m) { for(int i=1;i<=m;i++) scanf("%d",&arr[i]); ans=0; n--; dfs(1,1,1); cout<<ans<<endl; } return 0; }


链接:http://acm.hdu.edu.cn/showproblem.php?pid=4135

题解:

通常我们求1~n中与n互质的数的个数都是用欧拉函数! 但如果n比较大或者是求1~m中与n互质的数的个数等等问题,要想时间效率高的话还是用容斥原理!
//本题是求[a,b]中与n互质的数的个数,可以转换成求[1,b]中与n互质的数个数减去[1,a-1]与n互质的数的个数。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int maxn=70; long long prime[maxn]; long long solve(long long num,int m) { long long flag,temp,ans=0,i,j; for(i=1;i<(long long)(1<<m);i++) //用二进制来1,0来表示第几个素因子是否被用到,如m=3,三个因子是2,3,5,则i=3时二进制是011,表示第2、3个因子被用到 { flag=0,temp=1; for(j=0;j<m;j++) if(i&(long long)(1<<j)) //判断第几个因子目前被用到 { flag++; temp*=prime[j]; } if(flag&1) //容斥原理,奇加偶减 ans+=num/temp; else ans-=num/temp; } return ans; } int main() { int t,m; long long a,b,n,i; scanf("%d",&t); for(int cas=1;cas<=t;cas++) { cin>>a>>b>>n; m=0; for( i=2;i*i<=n;i++) //对n进行素因子分解 if(n&&n%i==0) { prime[m++]=i; while(n&&n%i==0) n=n/i; } if(n>1) prime[m++]=n; printf("Case #%d: %I64dn",cas,b-solve(b,m)-(a-1-solve(a-1,m))); } return 0; }

转载于:https://www.cnblogs.com/wolf940509/p/6617110.html

最后

以上就是潇洒月亮最近收集整理的关于组合计数问题中容斥原理的应用的全部内容,更多相关组合计数问题中容斥原理内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(82)

评论列表共有 0 条评论

立即
投稿
返回
顶部