容斥原理解释

刺骨的言语ヽ痛彻心扉 2022-03-18 07:04 237阅读 0赞

容斥原理各种地方各种解释，又是画图又是举例，但是我单单觉得百度百科解释的很好！

### 容斥原理：在[计数][Link 1]时，必须注意没有重复，没有遗漏。为了使[重叠][Link 2]部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目[排斥][Link 3]出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。   ###

## 对于实际问题的应用 ##

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

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

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

### 一个简单的排列问题 ###

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

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

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

![016.png][]

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

![017.png][]

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

### （0,1,2）序列问题 ###

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

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

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

![018.png][]

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

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

![019.png][]

### 方程整数解问题 ###

给出一个方程：

![020.png][]

其中![021.png][]。

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

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

![022.png][]

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

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

![023.png][]

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

![024.png][]

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

![025fixed.png][]

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

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

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

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

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

![026.png][]

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

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

关于此问题的最终实现：

int solve (int n, int r) {  
      
            vector<int> p;  
      
            for (int i=2; i*i<=n; ++i)  
      
                   if (n % i == 0) {  
      
                           p.push_back (i);  
      
                           while (n % i == 0)  
      
                                   n /= i;  
      
                   }  
      
            if (n > 1)  
      
                   p.push_back (n);  
      
       
      
            int sum = 0;  
      
            for (int msk=1; msk<(1<<p.size()); ++msk) {  
      
                   int mult = 1,  
      
                           bits = 0;  
      
                   for (int i=0; i<(int)p.size(); ++i)  
      
                           if (msk & (1<<i)) {  
      
                                   ++bits;  
      
                                   mult *= p[i];  
      
                           }  
      
       
      
                   int cur = r / mult;  
      
                   if (bits % 2 == 1)  
      
                           sum += cur;  
      
                   else  
      
                           sum -= cur;  
      
            }  
      
       
      
            return r - sum;  
      
    }

[https://blog.csdn.net/m0\_37286282/article/details/78869512][https_blog.csdn.net_m0_37286282_article_details_78869512]

[Link 1]: https://baike.baidu.com/item/%E8%AE%A1%E6%95%B0/9276342
[Link 2]: https://baike.baidu.com/item/%E9%87%8D%E5%8F%A0/9009438
[Link 3]: https://baike.baidu.com/item/%E6%8E%92%E6%96%A5/10717656
[016.png]: /images/20220318/09b341ea922a49ea93901cd72cb9f8bb.png
[017.png]: /images/20220318/971ed78982114a5db014466402b3c69c.png
[018.png]: /images/20220318/2671394c27594776be32c41c7d2b8273.png
[0185.png]: /images/20220318/7b90d14ff25b4911ab19b03c8adf2053.png
[019.png]: /images/20220318/ef495cb0fb044260aaab82e34be5f22f.png
[020.png]: /images/20220318/8dfde913711f4b04811970a845c2a3aa.png
[021.png]: /images/20220318/b272651d7a4c4d57956d1feea2000776.png
[Link 4]: https://www.baidu.com/s?wd=%E5%A4%B9%E6%9D%BF&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[022.png]: /images/20220318/f114b82db7254496973ed7bbea2a5808.png
[023.png]: /images/20220318/5a87aacafb4240bfbf3f5e81bb2a2415.png
[024.png]: /images/20220318/c7d37688113e4ccd98179767c1e8e722.png
[025fixed.png]: /images/20220318/3b3b4173e9ec4ce4bf0d8ee192c5a50f.png
[026.png]: /images/20220318/152d2ba3a9484c1994f142b6228ed204.png
[Link 5]: http://lib.csdn.net/base/datastructure
[https_blog.csdn.net_m0_37286282_article_details_78869512]: https://blog.csdn.net/m0_37286282/article/details/78869512