大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
容斥原理的证明
原链接地址
我们要证明下面的等式：
其中B代表全部Ai的集合
我们需要证明在Ai集合中的任意元素，都由右边的算式被正好加上了一次（注意如果是不在Ai集合中的元素，是不会出现在右边的算式中的）。
假设有一任意元素在k个Ai集合中（k>=1），我们来验证这个元素正好被加了一次：
当size(C)=1时，元素x被加了k次。
当size(C)=2时，元素x被减了C(2,k)次，因为在k个集合中选择2个，其中都包含x。
当size(C)=3时，元素x被加了C(3,k)次。
……
当size(C)=k时，元素x被加/减了C(k,k)次，符号由sign(-1)^(k-1)决定。
当size(C)>k时，元素x不被考虑。
然后我们来计算所有组合数的和。
由二项式定理，我们可以将它变成：
我们把x取为1，这时
表示1-T（其中T为x被加的总次数），所以
，证明完毕。
（自己画的图示理解）
题目
能满足一定数目匹配的字符串的个数问题
给出n个匹配串，它们长度相同，其中有一些’?’表示待匹配的字母。然后给出一个整数k，求能正好匹配k个匹配串的字符串的个数。更进一步，求至少匹配k个匹配串的字符串的个数。
首先我们会发现，我们很容易找到能匹配所有匹配串的字符串。只需要对比所有匹配串，去在每一列中找出现的字母（或者这一列全是’?’，或者这一列出现了唯一的字母，否则这样的字符串就存在），最后所有字母组成的单词即为所求。
现在我们来学习如何解决第一个问题：能正好匹配k个匹配串的字符串。
我们在n个匹配串中选出k个，作为集合X，统计满足集合X中匹配的字符串数。求解这个问题时应用容斥原理，对X的所有超集进行运算，得到每个X集合的结果：
此处f(Y)代表满足匹配集合Y的字符串数。
如果我们将所有的ans(X)相加，就可以得到最终结果：
这样，就得到了一个复杂度
的解法。
这个算法可以作一些改进，因为在求解ans(X)时有些Y集合是重复的。
回到利用容斥原理公式可以发现，当选定一个Y时，所有 
中X的结果都是相同的，其符号都为
。所以可以用如下公式求解：
这样就得到了一个复杂度
的解法。
现在我们来求解第二个问题：能满足至少k个匹配的字符串有多少个。
显然的，我们可以用问题一的方法来计算满足k到n的所有结果。问题一的结论依然成立，不同之处在于这个问题中的X不是大小都为k的，而是>=k的所有集合。
如此进行计算，最后将f(Y)作为另一个因子：将所有的ans做和，有点类似二项式展开：
在《具体数学》( Graham, Knuth, Patashnik. “Concrete Mathematics” [1998] )中，介绍了一个著名的关于二项式系数的公式：
根据这个公式，可以将前面的结果进行化简：
那么，对于这个问题，我们也得到了一个
的解法：
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/215448.html原文链接：https://javaforall.net
