对容斥原理的描述

容斥原理是一种重要的组合数学方法，可以让你求解任意大小的集合，或者计算复合事件的概率。

描述

       容斥原理可以描述如下：

         要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。

对于实际问题的应用

       容斥原理的理论需要通过例子才能很好的理解。

         首先，我们用三个简单的例子来阐释这个理论。然后会讨论一些复杂问题，试看如何用容斥原理来解决它们。

         其中的“寻找路径数”是一个特殊的例子，它反映了容斥问题有时可以在多项式级复杂度内解决，不一定需要指数级。

一个简单的排列问题

       由0到9的数字组成排列，要求第一个数大于1，最后一个数小于8，一共有多少种排列？

         我们可以来计算它的逆问题，即第一个元素<=1或者最后一个元素>=8的情况。

         我们设第一个元素<=1时有X组排列，最后一个元素>=8时有Y组排列。那么通过容斥原理来解决就可以写成：

       

         经过简单的组合运算，我们得到了结果：

         

         然后被总的排列数10!减，就是最终的答案了。

（0,1,2）序列问题

       长度为n的由数字0，1，2组成的序列，要求每个数字至少出现1次，这样的序列有多少种？

         同样的，我们转向它的逆问题。也就是不出现这些数字的序列 不出现其中某些数字的序列。

         我们定义Ai(i=0…2)表示不出现数字i的序列数，那么由容斥原理，我们得到该逆问题的结果为：

           可以发现每个Ai的值都为2^n（因为这些序列中只能包含两种数字）。而所有的两两组合都为1（它们只包含1种数字）。最后，三个集合的交集为0。（因为它不包含数字，所以不存在）

        要记得我们解决的是它的逆问题，所以要用总数减掉，得到最终结果：

         

方程整数解问题

       给出一个方程：

       

         其中。

         求这个方程的整数解有多少组。

         我们先不去理会xi<=8的条件，来考虑所有正整数解的情况。这个很容易用组合数来求解，我们要把20个元素分成6组，也就是添加5块“夹板”，然后在25个位置中找5块“夹板”的位置。

         

         然后通过容斥原理来讨论它的逆问题，也就是x>=9时的解。

         我们定义Ak为xk>=9并且其他xi>=0时的集合，同样我们用上面的添加“夹板”法来计算Ak的大小，因为有9个位置已经被xk所利用了，所以：

         

         然后计算两个这样的集合Ak、Ap的交集：

         

         因为所有x的和不能超过20，所以三个或三个以上这样的集合时是不能同时出现的，它们的交集都为0。最后我们用总数剪掉用容斥原理所求逆问题的答案，就得到了最终结果：

         

求指定区间内与n互素的数的个数：

       给出整数n和r。求区间[1;r]中与n互素的数的个数。

         去解决它的逆问题，求不与n互素的数的个数。

         考虑n的所有素因子pi(i=2…k)

         在[1;r]中有多少数能被pi整除呢？它就是：

       

         然而，如果我们单纯将所有结果相加，会得到错误答案。有些数可能被统计多次（被好几个素因子整除）。所以，我们要运用容斥原理来解决。

         我们可以用2^k的求出所有的pi组合，然后计算每种组合的pi乘积，通过容斥原理来对结果进行加减处理。

　　　如求[1,10]中与6互素的数有多少个：首先去解决它的逆问题，求不与n互素的数的个数。

　　　6的素因子有2,3；那么sum=10/2+10/3-10/(2*3)=5+3-1=7；

　　　所以[1,10]中与6互素的数有10-7=3（为5,7,9）；

　　　sum=10/2+10/3-10/(2*3)=5+3-1=7；公式中的分子为{2,3}的非空子集，每个子集都可以用二进制表示：10（选了2没选3）,01（选了3没选2）,11（选了2选了3）

代码实现

二进制实现：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #define ll long long 8 using namespace std; 9 vector
           
            p;//存放质因数10 int prime[5000]11 int visit[5000];12 //用筛法初始化40000以内的质数，将质数存放在prime数组中，m记录大小13 void init()14 {15 k=0;16 memset(visit,0,sizeof(visit));17 for(int i=2;i<5000;i++)18 {19 if(!visit[i])prime[k++]=i;20 for(int j=0;j
            
             <5000;j++)21 {22 visit[i*prime[j]]=1;23 if(i%prime[j]==0)break;24 }25 }26 }27 //对n分解质因数28 void factor(int n)29 {30 for(int i=0;i
             
              
               1)p.push_back(n);42 }43 //用二进制实现容斥原理,求区间[1,r]内与n互素的数的个数44 int slove(int r)45 {46 int sum=0;47 for(i=1;i<1<
              
             
            
           
          
         
        
       
      
     

dfs实现：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define ll long long 7 using namespace std; 8 int a[30],ans,k; 9 int n,m;10 int gcd(ll a,ll b)11 {12     return b==0?a:gcd(b,a%b);13 }14 void dfs(ll cur,ll lcm,int cnt)15 {16     lcm=a[cur]/gcd(a[cur],lcm)*lcm;//dfs遍历实现分子遍历17     if(cnt&1)18     ans+=(n-1)/lcm;19     else20     ans-=(n-1)/lcm;21     for(int i=cur+1;i
         
        
       
      
     

队列数组实现：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 __int64 fac[100000]; 8 __int64 k; 9 void init(__int64 n)10 {11     int i;k=0;12     for(i=2;i*i
          
           1)25 fac[k++]=n;26 }27 __int64 haha(__int64 n)28 {29 __int64 ha[10000],i,j,m,t=0,num=0;30 ha[t++]=-1;31 for(i=0;i