问题提出
有n个条件，要求不重复统计满足一到n个条件的所有可能数。
容斥原理
要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。
∑
i
:
1
m
(
−
1
)
i
+
1
\sum_{i:1}^m(-1)^{i+1}
∑i:1m(−1)i+1
(
m
i
)
m \choose i
(im)cnt[i]
cnt[m] 记录所有 满足m个条件的可能数。
下面来证明：
其本质是：集合求并。
贡献法
针对某个元素（某种情况）,它在m个集合中（符合m个条件）:
统计符合m个条件的情况数是：它被统计
(
m
m
)
m \choose m
(mm)次。
统计符合m-1个条件的
⋯
\cdots
⋯
(
m
m
−
1
)
m \choose m-1
(m−1m)次
⋮
\vdots
⋮
统计符合1个条件的
⋯
\cdots
⋯
(
m
1
)
m \choose1
(1m)次
它应该被统计一次，下面来证明：
∑
i
:
1
m
(
−
1
)
i
+
1
\sum_{i:1}^m(-1)^{i+1}
∑i:1m(−1)i+1
(
m
i
)
m \choose i
(im)
≡
1
\equiv 1
≡1
∑
i
:
1
m
(
−
1
)
i
+
1
\sum_{i:1}^m(-1)^{i+1}
∑i:1m(−1)i+1
(
m
i
)
m \choose i
(im) = -
∑
i
:
1
m
(
−
1
)
i
\sum_{i:1}^m(-1)^{i}
∑i:1m(−1)i
(
m
i
)
m \choose i
(im) = Y
-Y+1 =
∑
i
:
0
m
(
−
1
)
i
\sum_{i:0}^m(-1)^i
∑i:0m(−1)i
(
m
i
)
m \choose i
(im)
根据二项式定理：-Y+1== (-1+1)m = 0
→
\rightarrow
→ Y =1
相关知识点
帕斯卡法则
从n个不同的物品中选择m个，我读书的时候，是如下表示的：
C
n
m
_n^m
nm ,latex公式是如下表示的：
(
n
m
)
n \choose m
(mn)。
帕斯卡法则：
(
n
m
)
n \choose m
(mn) =
(
n
−
1
m
)
{n-1} \choose m
(mn−1) +
(
n
−
1
m
−
1
)
{n-1} \choose m-1
(m−1n−1)
分别对应n选择m的两种情况：
第一个物品没选择 和第一个物品选择。
二项式定理
二项式定理（英语：binomial theorem），又称牛顿二项式定理。
(
x
+
y
)
n
=
∑
i
:
0
n
(
n
i
)
x
i
y
n
−
i
(x+y)^n= \sum_{i:0}^n{n \choose i}x^iy^{n-i}
(x+y)n=i:0∑n(in)xiyn−i
下面用数学归纳法证明。
当n=1是
∑
i
:
0
1
(
n
i
)
x
i
y
n
−
i
=
x
0
y
1
+
x
1
y
0
=
y
+
x
\sum_{i:0}^1{n \choose i}x^iy^{n-i}=x^0y^1+x^1y^0=y+x
∑i:01(in)xiyn−i=x0y1+x1y0=y+x 得证。
下面来证明n=m成立，则n=m+1也成立。
(
x
+
y
)
m
+
1
=
x
(
x
+
y
)
m
+
y
(
x
+
y
)
m
=
x
∑
j
:
0
m
(
m
j
)
x
j
y
m
−
j
+
y
∑
k
:
0
m
(
m
k
)
x
k
y
m
−
k
根据假设
=
∑
j
:
0
m
(
m
j
)
x
j
+
1
y
m
−
j
+
∑
k
:
0
m
(
m
k
)
x
k
y
m
−
k
+
1
x
、
y
提到累加内
=
⋯
∑
k
:
1
m
(
m
k
)
x
k
y
m
−
k
+
1
+
y
m
+
1
提取
k
=
=
0
，式一
=
∑
k
:
1
m
+
1
(
m
k
−
1
)
x
k
y
m
−
k
+
1
⋯
设
j
=
k
−
1
，及
k
=
j
+
1
=
∑
k
:
1
m
(
m
k
−
1
)
x
k
y
m
−
k
+
1
+
x
m
+
1
⋯
提取
k
=
=
m
+
1
式二
=
∑
k
:
1
m
(
(
m
k
−
1
)
+
(
m
k
)
)
x
k
y
m
−
k
+
1
+
⋯
式一式二的累加部分结合
=
∑
k
:
1
m
(
m
+
1
k
)
x
k
y
m
−
k
+
1
+
⋯
帕斯卡法则
式一余下的部分就是
k
=
=
0
,
式二余下的部分就是
k
=
m
+
1
得证
(x+y)^{m+1}=x(x+y)^m+y(x+y)^m \\ = x\sum_{j:0}^m {m \choose j} x^jy^{m-j}+y\sum_{k:0}^m{m \choose k}x^ky^{m-k} \quad 根据假设 \\ = \sum_{j:0}^m{m \choose j}x^{j+1}y^{m-j}+\sum_{k:0}^m{m \choose k}x^ky^{m-k+1} \quad x、y提到累加内 \\ = \cdots \sum_{k:1}^m{m \choose k}x^ky^{m-k+1}+y^{m+1} \quad提取k==0，式一 \\ =\sum_{k:1}^{m+1}{m \choose k-1}x^ky^{m-k+1} \cdots \quad 设j=k-1，及k=j+1 \\ =\sum_{k:1}^{m}{m \choose k-1}x^ky^{m-k+1}+ x^{m+1} \cdots \quad 提取k==m+1 式二\\ =\sum_{k:1}^{m}({m \choose k-1}+{m \choose k})x^ky^{m-k+1} +\cdots \quad 式一式二的累加部分结合\\ =\sum_{k:1}^{m}{m+1 \choose k}x^ky^{m-k+1} +\cdots \quad 帕斯卡法则 \\ 式一余下的部分就是k==0,式二余下的部分就是k=m+1 得证
(x+y)m+1=x(x+y)m+y(x+y)m=xj:0∑m(jm)xjym−j+yk:0∑m(km)xkym−k根据假设=j:0∑m(jm)xj+1ym−j+k:0∑m(km)xkym−k+1x、y提到累加内=⋯k:1∑m(km)xkym−k+1+ym+1提取k==0，式一=k:1∑m+1(k−1m)xkym−k+1⋯设j=k−1，及k=j+1=k:1∑m(k−1m)xkym−k+1+xm+1⋯提取k==m+1式二=k:1∑m((k−1m)+(km))xkym−k+1+⋯式一式二的累加部分结合=k:1∑m(km+1)xkym−k+1+⋯帕斯卡法则式一余下的部分就是k==0,式二余下的部分就是k=m+1得证
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
QQ群名片
评论记录：
回复评论：