1. 概念

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

     ２.举例

（１）如果被计数的事物有A，B两类，那么，A类和B类元素个数总和=A类元素个数+B类元素个数-即使A类又是B类元素个数。

那么公式就是：

             |A∪B|  = |A| + |B| - |A∩B| 

可以用下面的图表示（也叫韦恩图）：

U表示全集（整个集合），A表示符合A类的数量，B表示符合B类的数量，I表示既不符合A也不符合B的数量，AB表示既符合A也符合B的数量，则U-I=A+B-AB。

（2）如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数-既是A类又是B类的元素个数-既是A类又是C类的元素个数-既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。

            |A∪B∪C|  = |A| + |B| + |C|  - |A∩B| -  |B∩C| - | C∩A | + |A∩B∩C|

可以用下面的图表示：

U表示整个大集合，A表示符合A类的数量，B表示符合B类的数量，C表示符合C类的数量，I表示既不符合A也不符合B还不符合C的数量，AB表示既符合A也符合B的数量，BC表是同时符合B和C的数量，AC表示既符合A也符合C的数量，ABC表示同时符合A、B、C的数量。

根据容斥原理的定义，先不考虑重叠，把某内容的所有对象数目先计算出来（即A+B+C）；再剔除重复计算的数目，AB这部分被计算了两次，也就是重复了一次，要剪掉，同理BC，AC也要个减掉一次；

那ABC呢？在A+B+C中我们把ABC统计了三次，所以理论上需要减掉两次，但是ABC同时又在AB、AC、BC中，也就是说我们减去AB的时候已经减了一次ABC，减去BC的时候又减了一次ABC，减AC的时候再一次减掉了ABC，即ABC总共减了三次。所以就需要额外再加回来一次。

那么等量关系就变成了U-I=A+B+C-AB-AC-BC+ABC

    3.例题

（1）为了发展体育运动，学校这学期开了体育兴趣课，学生需要从篮球和足球中选，允许两个同时选或同时不选。一个班级有50人，选了篮球的有32人，选了足球的有21人，两种都选了的有17人。问：有多少同学两种都没选。

如上图所示，篮球32人和足球21人，用总数50减去篮球再减去足球，中间重叠的部分被减了两次，所以再加一个中间重叠部分。50-32-21+17=14人。

（2）某校六⑴班有学生55人，每人在暑假里都参加体育训练队，其中参加足球队的有22人，参加排球队的有23人，参加游泳队的有24人，足球、排球都参加的有11人，足球、游泳都参加的有10人，排球、游泳都参加的有9人，问：三项都参加的有多少人？

我们假设足球队是A，排球队是B，游泳队是C。那么根据公式　 |A∪B∪C|  = |A| + |B| + |C|  - |A∩B| -  |B∩C| - | C∩A | + |A∩B∩C|　可以得出。

    55 = 22+23+24-11-10-9 +  |A∩B∩C| 。该式子计算得：16

（3）   假设班里有50名学生，每个人都必须选修一门运动科目，选修篮球的有15人，选修足球的有20人，选修乒乓球的有30人，同时选修篮球和足球的有10人，同时选修乒乓球和足球的有18人，同时选修篮球和乒乓球的有12人，问选修了三门科目的有多少人？

    根据上面的公式，可以15+20+30-10-18-12 + x =50。得x=25。

    思考一下？

 4.常见题目类型：

（1）排列问题：

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

（2）序列问题：

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

（3）方程组整数解问题

   给出一个方程：x1+x2+x3+x4+x5+x6=20, 对于每个 0<=xi<=8，求解这个方程组有多少组解。

（3）区间内互素个数

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

(4)至少一个被整除问题

       给出n个整数ai和整数r。求在区间[1;r]中，至少能被一个ai整除的数有多少。

(5)匹配字符串个数问题

       给出n个匹配串，它们长度相同，其中有一些’?’表示待匹配的字母。然后给出一个整数k，求能正好匹配k个匹配串的字符串的个数。更进一步，求至少匹配k个匹配串的字符串的个数。

(6)路径数据问题

    在一个的n*m方格阵中，有k个格子是不可穿越的墙。一开始在格子(1,1)（最左下角的格子）中有一个机器人。这个机器人只能向上或向右行进，最后它将到达位于格子(n,m)的笼子里，其间不能经过障碍物格子。求一共有多少种路线可以到达终点。

(7)数组四元组问题

       给出n个数a1,a2,a3....an，从其中选出4个数，使它们的最大公约数为1，问总共有多少中取法。

(8)和睦数三元组个数问题

（9）错排问题

【题目描述】

【输入描述】

【输出描述】

对于每组数据，输出一行，包含一个“YES”或者“NO”。

【样例输入】

2  3  4 1 1  5  5 4 3 2 1

【样例输出】

NO  YES

一、欧几里得算法

我们前面学过求最大公约数的算法：欧几里得算法（又叫辗转相除法） ，一般缩写是gcd，在C++中经常写成如下形式：

int gcd(int a,int b)     {        if(a%b==0)           return b;       else           return gcd(b,a%b);   }

原理就是代码中比较核心的 gcd(b，a%b)，这个定理用文字描述就是:

用a除以b（这里是a>b,当然，在程序编程中，求两个数的最大公约数，可以不限a和b的大小，a<b也就是多一次循环）得到结果q和余数r，再用除数b除以余数r 再得到一个余数，再用除数除以余数，…如此循环，直到余数为0，那么此时的除数就是最大公因数。

想要证明gcd(a,b) = gcd(b,a%b)，需要简单了解下面两个引理：

• 若d是a和b的公约数，那么d也是b和c的公约数（c为a%b）

• 若d是b和c的公约数（c为a%b），那么d也是a和b的公约数

这两个引理的是什么意思呢，拿第一个来说；

假设一个数d是a的因子，也就是a=m*d，同时也是b的因子，b=n*d，那么a%b = a-w*b =  (m-w*n)*d；

由此可得，a的因子集合、b的因子集合和c的因子集合是相同的；

然后利用上述定理当余数为0的时候，除数就是最大公约数；

二、扩展欧几里得算法

    从字面上看，扩展欧几里得算法就是把欧几里得算法进行了扩展，不仅能求a和b的最大公约数，还其他功能，比如:

• 求ax+by=m的任意一组解，最小整数解。

• 求模逆元（模反元素）

为了了解学习上面的公式，需要先了解一个裴属定理

【题目描述】

求m%n。

【输入描述】

两个数，m和n。

【输出描述】

m模n的值。

【样例输入】

3

【样例输出】

2

【数据范围】

对于30%的数据， 1<m<10^18

对于70%的数据， m>10^18

【题目描述】

    求解 (2^0 + 2^1 + 2^2+ ... + 2^n) % 2333

【输入描述】

    一行，一个整数n。

【输出描述】

    一行，表达式的正确结果

【样例输入】

2

【样例输出】

7

【题目描述】

有n个非负整数，请从这n个非负整数中，选出m个数，在不改变m个数的顺序的情况下，构成一个新数列，要求该数列的中相邻两个数的差值绝对值的和尽可能小。

请问，这个最小的差值绝对值的和是多少？

比如：有5个数是2 1 8 5 9，如果从中选3个数，不改变顺序的情况下，要求相邻2个数的差值绝对值的和最小，选数方法可以是：2 1 5，差值绝对值的和是|1-2|+|5-1|=5。

【输入描述】

第1行输入2个整数，分别是n和m。（2≤m≤n≤100）

第2行，有n个非负整数，数字之间用空格隔开。

【输出描述】

按题意输出最小的差值绝对值的和。（本题保证计算出来的结果，在int的范围内）

【样例输入】

5 3  2 1 8 5 9

【样例输出】

5

【题目描述】

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹的枚数和导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，每个数据之间至少有一个空格），计算这套系统最多能拦截多少导弹。

【输入描述】

第1行有1个整数n，代表导弹的数量。（n<=1000）

第2行有n个整数，代表导弹的高度。（雷达给出的高度数据是不大于30000的正整数）

【输出描述】

第一行：最多能拦截的导弹数；

第二行：要拦截所有导弹最少要配备的系统数。

【样例输入】

8  389  207  155  300  299  170  158  65

【样例输出】

6