首页 > 代码库 > 容斥原理学习

容斥原理学习

2024-07-29 05:33:12   223人阅读

简单入门题目: 

UVA10325   The lottery  http://vjudge.net/vjudge/contest/view.action?cid=53767#problem/A

设A[I]表示 是其中i个数的倍数的个数

SUM=A[1]-A[2]+A[3]-A[4]。。。。。

ANS=N-SUM;

代码如下：

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. #include <iostream>  
  2. #include <cstring>  
  3. #include <cstdio>  
  4. #define LL long long  
  5. using namespace std;  
  6.   
  7. LL a[15];  
  8.   
  9. LL gcd(LL a,LL b){  
  10.     if(b)  
  11.         return gcd(b,a%b);  
  12.     return a;  
  13. }  
  14.   
  15. LL lcm(LL a,LL b){  
  16.     return a/gcd(a,b)*b;  
  17. }  
  18.   
  19.   
  20. int main()  
  21. {  
  22.     int m;  
  23.     LL n,ans;  
  24.     while(cin>>n>>m){  
  25.         for(int i=0;i<m;i++)  
  26.         cin>>a[i];  
  27.         ans=0;  
  28.         for(int i=1;i<(1<<m);i++){  
  29.             LL l=1,flag=0;  
  30.             for(int j=0;j<m;j++){  
  31.                 if((1<<j)&i){  
  32.                     l=lcm(l,a[j]);  
  33.                     if(l>n) break;  
  34.                     flag++;  
  35.                 }  
  36.             }  
  37.             if(flag&1)  
  38.                 ans+=n/l;  
  39.             else  
  40.                 ans-=n/l;  
  41.         }  
  42.         cout<<n-ans<<endl;  
  43.     }  
  44.     return 0;  
  45. }  


SPOJ   Another Game With Numbers   http://vjudge.net/vjudge/contest/view.action?cid=53767#problem/C

思路同上。

代码如下：

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. #include <iostream>  
  2. #include <cstring>  
  3. #include <cstdio>  
  4. #define LL long long  
  5. using namespace std;  
  6.   
  7. LL a[15];  
  8.   
  9. LL gcd(LL a,LL b){  
  10.     if(b)  
  11.         return gcd(b,a%b);  
  12.     return a;  
  13. }  
  14.   
  15. LL lcm(LL a,LL b){  
  16.     return a/gcd(a,b)*b;  
  17. }  
  18.   
  19.   
  20. int main()  
  21. {  
  22.     int m;  
  23.     LL n,ans;  
  24.     while(cin>>n>>m){  
  25.         for(int i=0;i<m;i++)  
  26.         cin>>a[i];  
  27.         ans=0;  
  28.         for(int i=1;i<(1<<m);i++){  
  29.             LL l=1,flag=0;  
  30.             for(int j=0;j<m;j++){  
  31.                 if((1<<j)&i){  
  32.                     l=lcm(l,a[j]);  
  33.                     if(l>n) break;  
  34.                     flag++;  
  35.                 }  
  36.             }  
  37.             if(flag&1)  
  38.                 ans+=n/l;  
  39.             else  
  40.                 ans-=n/l;  
  41.         }  
  42.         cout<<n-ans<<endl;  
  43.     }  
  44.     return 0;  
  45. }  

UVA 11806 Cheerleaders   http://vjudge.net/vjudge/contest/view.action?cid=53767#problem/B


分析：

题目的意思就是 m*n个格子 在上面放k个  且第一行第一列最后一行最后一列都必须得放

反面考虑，考虑所有不符合条件的情况 ，一共有15种 ，然后用所有的情况减去即可；

代码如下：

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. #include <iostream>  
  2. #include <cstring>  
  3. #include <cstdio>  
  4. #define LL long long  
  5. using namespace std;  
  6.   
  7. const int maxn = 410;  
  8.   
  9. const int mod = 1000007;  
  10.   
  11. int com[maxn][maxn];  
  12.   
  13. void init(){  
  14.     memset(com,0,sizeof(com));  
  15.     for(int i=0;i<maxn;i++)  
  16.         com[i][0]=1;  
  17.     for(int i=1;i<maxn;i++){  
  18.         for(int j=1;j<=i;j++)  
  19.             com[i][j]=(com[i-1][j-1]%mod+com[i-1][j]%mod)%mod;  
  20.     }  
  21. }  
  22.   
  23. int n,m,k;  
  24.   
  25. int solve(){  
  26.     int ans=0;  
  27.     for(int i=1;i<(1<<4);i++){  
  28.         int num=0,r=n,c=m;  
  29.         if(i&1) r--,num++;  
  30.         if(i&2) r--,num++;  
  31.         if(i&4) c--,num++;  
  32.         if(i&8) c--,num++;  
  33.         if(num%2==0)  
  34.             ans=(ans+mod-com[r*c][k])%mod;  
  35.         else  
  36.             ans=(ans+com[r*c][k])%mod;  
  37.     }  
  38.     return (com[m*n][k]-ans+mod)%mod;  
  39. }  
  40.   
  41. int main()  
  42. {  
  43.     int t,cnt=1;  
  44.     init();  
  45.     cin>>t;  
  46.     while(t--){  
  47.         cin>>n>>m>>k;  
  48.         int ans=solve();  
  49.         printf("Case %d: %d\n",cnt++,ans);  
  50.     }  
  51.     return 0;  
  52. }  




POJ 3904  Sky Code :http://poj.org/problem?id=3904

分析：

反面考虑，求出取出四个数的所有情况中 GCD(A,B,C,D)!=1的情况；我们只需将每一个数都给素因子分解，然后看使用不重复的素因子所能组成的因子的个数，并统计组成该因子 的素因子的个数

例如  形成的的因子2 的个数 为a，形成因子3的个数为b，形成6的因子的个数为c  则cnt=com(a,4)+com(b,4)-com(c,4);

代码如下：

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. #include<iostream>  
  2. #include<cstdlib>  
  3. #include<stdio.h>  
  4. #include<memory.h>  
  5. #define maxn 10005  
  6. using namespace std;  
  7.   
  8. long long Count[maxn];  
  9. long long num[maxn];  
  10. long long p[maxn];  
  11. long long prime[maxn];  
  12.   
  13. void init()  
  14. {  
  15.     memset(p,0,sizeof(p));  
  16.     memset(num,0,sizeof(num));  
  17.     for(long long i=4;i<maxn;i++)  
  18.     p[i]=i*(i-1)*(i-2)*(i-3)/24;  
  19. }  
  20. void solve(long long  n)  
  21. {  
  22.     long long  tol=0;  
  23.     for(long long  i=2;i*i<=n;i++)  
  24.     {  
  25.         if(n%i==0)  
  26.         {  
  27.             prime[tol++]=i;  
  28.         }  
  29.         while(n%i==0)  
  30.             n/=i;  
  31.     }  
  32.     if(n!=1)  
  33.     prime[tol++]=n;  
  34.     for(long long  i=1;i<(1<<tol);i++)  
  35.     {  
  36.         long long k=1;  
  37.         long long sum=0;  
  38.         for(long long  j=0;j<tol;j++)  
  39.         {  
  40.             if(i&(1<<j))  
  41.             {  
  42.                 k*=prime[j];  
  43.                 sum++;  
  44.             }  
  45.         }  
  46.         Count[k]++;//记录当前因子的个数  
  47.         num[k]=sum;//记录当前因子是由多少个素因子组成  
  48.     }  
  49.   
  50. }  
  51. int main()  
  52. {  
  53.    init();  
  54.    long long  n;  
  55.    long long  m;  
  56.    while(scanf("%lld",&n)!=EOF)  
  57.    {  
  58.        memset(Count,0,sizeof(Count));  
  59.        for(long long  i=0;i<n;i++)  
  60.        {  
  61.            scanf("%lld",&m);  
  62.            solve(m);  
  63.        }  
  64.        long long ans=0;  
  65.        for(long long  i=0;i<maxn;i++)  
  66.        {  
  67.            if(Count[i])  
  68.            {  
  69.                if(num[i]%2)  
  70.                {  
  71.                    ans+=p[Count[i]];  
  72.                }  
  73.                else  
  74.                ans-=p[Count[i]];  
  75.            }  
  76.        }  
  77.        cout<<p[n]-ans<<endl;  
  78.    }  
  79.    return 0;  
  80. }   

SPOJ 4168 Square-free integers

http://vjudge.net/vjudge/contest/view.action?cid=53767#problem/E

分析：

求1~n中有多少个数可以写成 x^2,我们可以把这样的数写成 p^(2*q),

1~n中这样的数的个数为n/(p*p);中间重复的数我们根据容斥原理可以去掉

系数为莫比乌斯函数值

代码如下：

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstring>  
  4. using namespace std;  
  5.   
  6. typedef long long LL;  
  7.   
  8. const int maxn = 10000100;  
  9.   
  10. bool p[maxn];  
  11.   
  12. int mu[maxn],prime[maxn],cnt;  
  13.   
  14.   
  15. //线性筛选求莫比乌斯反演  
  16. void Init()  
  17. {  
  18.     memset(p,0,sizeof(p));  
  19.     mu[1] = 1;  
  20.     cnt = 0;  
  21.     for(int i=2; i<maxn; i++){  
  22.         if(!p[i]){  
  23.             prime[cnt++] = i;  
  24.             mu[i] = -1;  
  25.         }  
  26.         for(int j=0; j<cnt&&i*prime[j]<maxn; j++){  
  27.             p[i*prime[j]] = 1;  
  28.             if(i%prime[j]) mu[i*prime[j]] = mu[prime[j]]*mu[i];  
  29.             else  
  30.                 break;  
  31.         }  
  32.     }  
  33. }  
  34.   
  35. int main()  
  36. {  
  37.     Init();  
  38.     LL n,ans;  
  39.     int ca;  
  40.     scanf("%d",&ca);  
  41.     while(ca--){  
  42.         scanf("%lld",&n);  
  43.         ans=0;  
  44.         for(int i=1;i<=n/i;i++){  
  45.             if(mu[i])  
  46.                 ans+=n/i/i*mu[i];  
  47.         }  
  48.         printf("%lld\n",ans);  
  49.     }  
  50.     return 0;  
  51. }  

容斥原理学习


联系
我们