容斥原理学习笔记

引入

用一个简单的例子来引入容斥：

这个例子可以说是非常经典，一共有三种活动 {1,2,3}{1,2,3} 。
同时你可以查询 f(S)f(S) 会返回参加了 SS 集合中活动的人的个数。
现在的问题是求至少有多少个人参加了活动。

我记得这个是班上高一上集合时的作业最后一题。
看上去非常奇怪，但是可以发现如果根据题目意思画一个韦恩图就是非常简单的事了。
这里省略画图的过程，答案还是比较显然的：

f({1})+f({2})+f({3})−f({1,2})−f({1,3})−f({2,3})+f({1,2,3})

f({1})+f({2})+f({3})−f({1,2})−f({1,3})−f({2,3})+f({1,2,3})

前置知识

二项式定理

可以发现对于 (a+b)n(a+b)n 的各个位的系数和杨辉三角有很大的关系。
杨辉三角满足 Ti,j=Ti−1,j+Ti−1,j−1Ti,j=Ti−1,j+Ti−1,j−1 。
我们记 (nm)(nm) 表示组合数形如 CmnCmn 。
容易得到：

(nm)=Cmn=n!m!(n−m)!

(nm)=Cmn=n!m!(n−m)!

直接给出二项式定理的结论，证明的话直接归纳。

(a+b)n=n∑i=0(ni)aibn−i

(a+b)n=∑i=0n(ni)aibn−i

组合数的相关公式

其实上过小学的人都知道，组合数和杨辉三角也是对应的。

(ni)=(n−1i)+(n−1i−1)

(ni)=(n−1i)+(n−1i−1)

如果要证明的话可以直接化简一下式子。

(ni)=n!i!(n−i)!(n−1i)=(n−1)!i!(n−1−i)!=n!(n−i)i!n(n−i)!(n−1i−1)=(n−1)!(i−1)!(n−i)!=n!ii!n(n−i)!

(ni)(n−1i)(n−1i−1)=n!i!(n−i)!=(n−1)!i!(n−1−i)!=n!(n−i)i!n(n−i)!=(n−1)!(i−1)!(n−i)!=n!ii!n(n−i)!

式子化简到这一步也就是非常显然的了。

奇奇怪怪的知识（可能用不到）

在莫比乌斯反演中好像比较吃香，就是求和符号可以随便换位置。
具体就不举例子了。

正文

最简单的容斥还是之前引入的那个问题。
我们仍然记 f(S)f(S) 为参加了 SS 这个集合中所有活动的人的个数。
但是我们这次要从公式化的角度去得到答案，我们记 UU 表示所有的元素，则：

Ans=∑S⊆Uf(S)(−1)|s|+1

Ans=∑S⊆Uf(S)(−1)|s|+1

还是非常简单的，小学生画一个韦恩图都可以搞明白。

比较牛逼的容斥方法

首先我们令之前的 f(s)f(s) 查询操作改名为 q(s)q(s) 。
用 g(x)g(x) 表示一个在结合 xx 中的元素提供的贡献，f(x)f(x) 表示容斥系数。
他们的关系可以这样表示:

g(n)=n∑i=1(ni)f(i)

g(n)=∑i=1n(ni)f(i)

接下来我们可以发现，f(x)f(x) 可以通过递推得到。

g(n+1)=n+1∑i=1(n+1i)f(i)

g(n+1)=∑i=1n+1(n+1i)f(i)

因为当 i=n+1i=n+1 时 (n+1i)=(n+1n+1)=1(n+1i)=(n+1n+1)=1 ，所以可以直接提取出 f(n+1)f(n+1) 。

g(n+1)=n∑i=1(n+1i)f(i)+f(n+1)f(n+1)=g(n+1)−n∑i=1(n+1i)f(i)

g(n+1)=∑i=1n(n+1i)f(i)+f(n+1)f(n+1)=g(n+1)−∑i=1n(n+1i)f(i)

直接搞就可以啦。
听说还有多项式求逆的 O(nlogn)O(nlogn) 的做法，但是我不会，先咕一下。

一些应用或者入门题

1. 还是之前引入时的题目，可以进行一些转化。

直接套用公式就可以了，这里就再把式子放一下，不再进行解释：

Ans=∑S⊆Uf(S)(−1)|s|+1

Ans=∑S⊆Uf(S)(−1)|s|+1

2.错排问题

错排就是对于 1∼n1∼n 的排列 aiai ，对于所有的 ii ，满足 ai≠iai≠i 。
直接算贡献不太好算，计算出不合法也就是存在 ai=iai=i 的情况。
我们假设有 numnum 个位置满足 ai=iai=i ，那么剩下来的怎么拍都可以，也就是 (n−num)!(n−num)! 。
我们用 f(n)f(n) 表示长度为 nn 的排列的错排个数。
很容易列出下面的这个式子：

f(n)=n∑i=0(−1)i(ni)(n−i)!

f(n)=∑i=0n(−1)i(ni)(n−i)!

这个式子是非常显然的，现在来看看可不可以搞出一个递推式。

f(n+1)=n+1∑i=0(−1)i(n+1i)(n+1−i)!=n∑i=0(−1)i(n+1i)(n+1−i)!+(−1)n+1(n+1n+1)(n+1−n−1)!=(−1)n+1+n∑i=0(−1)i(n+1i)(n+1−i)!

f(n+1)=∑i=0n+1(−1)i(n+1i)(n+1−i)!=∑i=0n(−1)i(n+1i)(n+1−i)!+(−1)n+1(n+1n+1)(n+1−n−1)!=(−1)n+1+∑i=0n(−1)i(n+1i)(n+1−i)!

前面非常清楚了，现在来看后面的那一个部分：

Num=n∑i=0(−1)i(n+1i)(n+1−i)!=n∑i=0(−1)i(ni)×(n+1)×(n−i)!×(n+1)=(n+1)2n∑i=0(−1)i(ni)(n−i)!

Num=∑i=0n(−1)i(n+1i)(n+1−i)!=∑i=0n(−1)i(ni)×(n+1)×(n−i)!×(n+1)=(n+1)2∑i=0n(−1)i(ni)(n−i)!

可以发现现在和之前的式子

f(n)=n∑i=0(−1)i(ni)(n−i)!

f(n)=∑i=0n(−1)i(ni)(n−i)!

挂上了关系。
所以就可以得到递推式：

f(n)=(−1)n+nf(n−1)

f(n)=(−1)n+nf(n−1)

3.Hdu 上的一道简单题 Co-prime

题目描述：给你 ll ，rr 和 nn ，问 [l,r][l,r] 中有多少个数和 nn 互质。
其中 l,r≤1015l,r≤1015 ，n≤109n≤109 。

很容易发现，直接计算不太好算，所以采用类似前缀和的方法。
我们记录 f(i)f(i) 表示 [1,i][1,i] 中和 nn 互质数的个数，那么答案是 f(r)−f(l−1)f(r)−f(l−1) 。
现在来考虑怎么计算出 f(i) 。
发现最坏的情况下 n 只会有 10 个质因数组成，所以我们先对 n 质因数分解。
然后直接 pnum! 暴力枚举每一种可能性就可以了。
直接容斥，具体细节直接看代码：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
cpp
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define quad putchar(' ')
#define Enter putchar('\n')

using std::abs;
using std::pair;
using std::string;
using std::make_pair;

#define int long long

template <class T> void read(T &a);
template <class T> void write(T x);

template <class T, class ...rest> void read(T &a, rest &...x);
template <class T, class ...rest> void write(T x, rest ...a);

int T, l, r, n, num[50], tot, ok[50], ans1, ans2;

inline void get_prime(int n) {
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      num[++tot] = i;
      while (n % i == 0) n /= i;
    }
  } 
  if (n != 1) num[++tot] = n;
  return ;
}

inline void dfs(int k) {
  if (k > tot) {
    int chose = 0, tmp = -1, mul = 1;
    for (int i = 1; i <= tot; i++) {
      chose += ok[i];
      mul = mul * (ok[i] == 1 ? num[i] : 1);
    }
    if (chose % 2 == 0) tmp = 1;
    ans1 += (l - 1) / mul * tmp;
    ans2 += r / mul * tmp;
    return ;
  }
  ok[k] = 1; dfs(k + 1);
  ok[k] = 0; dfs(k + 1);
}

signed main(void) {
  read(T);
  for (int test = 1; test <= T; test ++) {
    tot = ans1 = ans2 = 0;
    memset(num, 0, sizeof(num));
    read(l, r, n); get_prime(n);
    dfs(1);
    printf("Case #%d: ", test);
    write(ans2 - ans1); Enter;
  }
  return 0;
}
/*
2
1 10 2
3 15 5
*/

template <class T> void read(T &a) {
  int s = 0, t = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') c = getchar(), t = -1;
  while (isdigit(c)) s = s * 10 + c - '0', c = getchar();
  a = s * t;
}
template <class T> void write(T x) {
  if (x == 0) putchar('0');
  if (x < 0) putchar('-'), x = -x;
  int top = 0, sta[50] = {0};
  while (x) sta[++top] = x % 10, x /= 10;
  while (top) putchar(sta[top] + '0'), top --;
  return ;
}

template <class T, class ...rest> void read(T &a, rest &...x) {
  read(a); read(x...);
}
template <class T, class ...rest> void write(T x, rest ...a) {
  write(x); quad; write(a...);
}
折叠