容斥原理（道理很简单，重在实践）

本文主要是介绍容斥原理（道理很简单，重在实践），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

在组合数学中如何求2或2个以上集合的并集中元素的个数，若这几个集合两两无关，也就是没有交集，可以用加法原理，这个比较好理解，把所有集合的大小加起来就行了。若出现交集，就需要使用容斥原理。

理解

我认为容斥原理就是一个把多算的那块去掉，多去掉的那块补上的过程，可能这么说比较抽象，但确实如此。

这里举个例子：

计数1到600之间不能被6整除的整数个数。

这里600个是包含能被6整除的个数，所以要把多算的那块去掉，从1开始每6个数都有一个可以被6整除，所以600/6 = 100答案就是600-100=500

这个例子是减法原理，但也是容斥原理最简单的例子。

这个例子抽象一下是对于有限集合S，有一个性质p不满足某个性质，那么求满足性质的集合大小。

将这个问题拓展一下，p1,p2,p3…pm不满足某个性质，这些不满足性质的集合对应的是 $A_i$ ,我们要求满足的集合大小。所求的对象个数可以由下面的交错表达式给出：
$\mid \overline{A_1}\bigcap\overline{A_2}\bigcap\cdots\bigcap\overline{A_m} \mid =\mid S \mid - \sum{\mid A_i \mid} + \sum{\mid A_i\bigcap A_j \mid} - \sum{\mid A_i\bigcap A_j \bigcap A_k\mid} + \cdots+(-1)^{m}\mid {A_1}\bigcap{A_2}\bigcap\cdots\bigcap{A_m}\mid$
根据上述的表达式我们可以解决

计数1到1000之间不能被5,6,8整除的整数个数

很明显|S| = 1000

|A1| = 1000/5 = 200

|A2| = 1000/6 = 166

|A3| = 1000/8=125

然后我们要求的交集部分

(A1,A2):1000/lcm(5, 6)=33

(A1,A3):1000/lcm(5, 8)=25

(A1,A2):1000/lcm(6, 8)=33

(A1,A2,A3):1000/lcm(5, 6, 8) = 8

答案：1000-（200+166+125）+（33+25+41）-8=600

题目

一班容斥原理的题目不能直接套那个公式，需要我们真正明白把多算的那块去掉，多去掉的那块补上的过程的含义

The Lottery

UVA - 10325

这道题和上面第二例子一样，只不过不能被N个数整除，只要枚举被1~N个数整除，把所有情况都找出来，套公式即可，这里值得注意的是lcm和gcd都具有结合律，也就是说lcm(a,b,c) = lcm(lcm(a,b),c)

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxm = 20;
ll num[maxm], n;
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);
}ll lcm(ll a, ll b) {return a / gcd(a, b) * b;
}
int m;
ll ans;
void dfs(int c, int cur, int i, ll now) {if(cur == c) {ans += ((c & 1) ? -1 : 1) * (n/now);return;}while(i < m) {dfs(c, cur+1, i+1, lcm(now, num[i]));i++;}
}
int main()
{// freopen("/Users/maoxiangsun/MyRepertory/acm/i.txt", "r", stdin);while(~scanf("%lld%d", &n, &m)) {for(int i = 0; i < m; i++) {scanf("%lld", num+i);}ans  = n;for(int i = 1; i <= m; i++) {dfs(i, 0, 0, 1);}printf("%lld\n", ans);}return 0;
}

Cheerleaders

UVA - 11806

这道题的意思是一个n*m的方格表，每个方格最多放一个东西，我们要放k个东西，问在上下左右那几条边都有东西的前提下有多少种方式。

也是套那个公式，最后可以推出这样的结果：
$k)+C((m-1)n,k))\\ +(C((n-2)m,k)+C((m-2)n,k)+4C((m-1)(n-1), k)\\ -2C(m-2)(n-1),k)-2C(C(m-1)(n-2),k) +C((m-2)(n-2), k);$
还有就是组合数取模问题，利用杨辉三角那个样子打表处理这种n*m不是很大，比较合适，再不行就用Lucas定理……

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const ll maxn = 420;
const ll mod = 1000007;
ll CC[maxn][maxn] = {0};
void init() {CC[0][0] = 1;for(ll i = 1; i < maxn; i++) {CC[i][0] = 1;for(ll j = 1; j <= i; j++) {CC[i][j] = (CC[i-1][j-1] + CC[i-1][j])%mod;}}
}
ll C(ll n, ll m) {return CC[n][m];
}
int main()
{ios::sync_with_stdio(false); cin.tie(0);ll n,m,k;ll T; init();cin >> T;int cas=0;while(T--) {cin >> n >> m >> k;ll ans =  (C(n*m,k)-(2*C((n-1)*m, k) + 2*(C(n*(m-1), k)) -C((m-2)*n, k) -C((n-2)*m, k) - 4*C((m-1)*(n-1) , k) + 2*C((m-2)*(n-1), k) + 2*C((m-1)*(n-2),k)-C((m-2)*(n-2), k) ) );while(ans < 0) {ans += mod;}cout << "Case "<<++cas<<": ";cout << ans % mod << endl; }return 0;
}

2018山东省赛F题

https://ac.nowcoder.com/acm/contest/123/F

这道题的意思是给出四个区间左右端点li，ri，从中取出x1,x2,x3,x4，问这四个值相邻元素不等的取法有多少种，可以用容斥想，S-不符合条件的总数。

情况1，只考虑两两相邻相等，可以分出四组来

情况2，在三个相邻相等和x1=x2&&x3=x4与x2=x3&&x1=x4公6组，不难发现在情况1中包含了情况2的可能所以要把多去的情况1加上去，加多少呢？加一倍，为啥？比如情况1在计算x1=x2的数量时已经计算了x3=x4的数量，而x3=x4的数量时又计算了x1=x2所以计算了两遍x1=x2&&x3=x4

情况3，x1=x2=x3=x4

这是最容易错的地方，我已开始做也是因为这wa了，为啥，情况1多算4次，情况2把6次减去了，情况3需要1次所以需要加上3倍的情况3才行！

代码：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
ll ans;
ll l[5],r[5];
const ll mod = 1e9 + 7;int main()
{int T; scanf("%d", &T);while(T--) {ans = 1;for(int i = 0; i < 4; i++) {// cin >> l[i] >> r[i];scanf("%lld%lld", &l[i], &r[i]);ans = ans * (r[i] - l[i] + 1) % mod;}ll left, right;for(int i = 0; i < 4; i++) {left = max(l[i], l[(i+1)%4]);right = min(r[i], r[(i+1)%4]);if(right >= left) ans=((ans-(right-left+1)*(r[(i+2)%4]-l[(i+2)%4]+1)%mod*(r[(i+3)%4]-l[(i+3)%4]+1)%mod)%mod+mod)%mod;} for(int i = 0; i < 4; i++) {left = max(l[i], max(l[(i+1)%4], l[(i+2)%4]));right = min(r[i], min(r[(i+1)%4], r[(i+2)%4]));if(right >= left) ans = (ans + (right - left + 1) * (r[(i+3)%4] - l[(i+3)%4] + 1)%mod)%mod;}ll l1,l2,r1,r2;for(int i = 0; i < 2; i++) {l1 = max(l[i], l[i+1]);r1 = min(r[i], r[i+1]);l2 = max(l[(i+2)%4], l[(i+3)%4]);r2 = min(r[(i+2)%4], r[(i+3)%4]);if(l1 <= r1 && l2 <= r2) {ans = (ans + (r1-l1+1)*(r2-l2+1)%mod)%mod;}}left = l[0];right = r[0];for(int i = 1; i < 4; i++) {left = max(l[i], left);right = min(r[i], right);}if(right >= left) {ans = (ans - (3*(right - left + 1))%mod + mod ) % mod;}printf("%lld\n", ans);}   return 0;
}