妈的好难理解啊 QAQ
经典容斥
容斥模型：
设有一些元素及一些条件 \(U=\{p_1,p_2,\dots,p_n\}\)。
有一个函数 \(f\)，\(f(S),S\subseteq U\) 表示至少满足 \(S\) 中的全部条件的元素的个数。
有一个函数 \(g\)，\(g(n)\) 表示一个满足 \(n\) 个条件的元素对答案的贡献。
依据 \(g\) 有一个函数 \(h\) 表示我们计算出的容斥系数。
容斥原理就告诉我们答案为
\[\sum_{S\in U}f(S)h(|S|) \]在这个式子中一个满足 \(n\ (n\geq 1)\) 个条件的元素对答案的贡献为（考虑它满足的条件集合怎么样被上式枚举）
\[\sum_{i=0}^n\binom{n}{i}h(i)=g(n) \]这个隐性递归式可以帮助我们计算 \(h\)，可以令 bot 在 \(O(n^2)\) 的时间开销下帮我们算容斥系数。
比如说我们需要计算至少满足一个条件的元素数量，那么就有
\[h(n)=[n\neq 0](-1)^{n-1} \]证明，对于每个满足 \(0\) 个条件的元素，它们的贡献是 \(0\)，对于每个满足 \(\geq 1\) 个条件的元素，它们的贡献是 \(1\)。
所以要有
\[g(n)=[n\neq 0] \]这就要求
\[\sum_{i=0}^n\binom{n}{i}h(i)=[n\neq 0] \]当 \(n=0\) 时得到 \(h(0)=0\)，当 \(n\geq 1\) 时左边为
\[\begin{aligned} &\sum_{i=0}^n\binom{n}{i}h(i)\\ =&\sum_{i=1}^n\binom{n}{i}(-1)^{i-1}\\ =&-\Bigg(\sum_{i=1}^n\binom{n}{i}(-1)^{i}\Bigg)\\ =&-\Bigg(\bigg(\sum_{i=0}^n\binom{n}{i}(-1)^i\times1^{n-i}\bigg)-1\Bigg)\\ =&-\Bigg(\Big((-1)+1\Big)^n-1\Bigg)\\ =&\ 1 \end{aligned}\]得证。
故满足至少一个条件的元素数量为
\[\sum_{S\subseteq U}[|S|\neq 0](-1)^{|S|-1}f(S) \]如果是满足至少 \(k\) 个条件的元素数量那么也只需在前面令 \(g(n)=[n\geq k]\) 算容斥系数就好了。
同样可以证明不满足任何条件的元素数量为
\[\sum_{S\subseteq U}(-1)^{|S|}f(S) \]有些时候我们会想求恰满足条件集合 \(T\) 的元素数量，感性理解一下，我们把 \(T\) 定义为 \(\emptyset\)，把 \(U\) 定义为所有 \(T\) 的超集，那么这个问题就转化成求不满足任何条件的元素数，也就是
\[\sum_{T\subseteq S\subseteq U}(-1)^{|S|-|T|}f(S) \]令元素为所有的字符排列，条件集合是 \(\{可以匹配 s_1,可以匹配 s_2,\dots,可以匹配 s_n\}\) 答案是
\[\begin{aligned} &\sum_{|T|=k}\sum_{T\subseteq S\subseteq U}(-1)^{|S|-k}f(S)\\ =&\sum_{S\subseteq U,|S|\geq k}\sum_{S\subseteq T,|S|=k}(-1)^{|S|-k}f(S)\\ =&\sum_{S\subseteq U,|S|\geq k}\binom{|S|}{k}(-1)^{|S|-k}f(S)\\ \end{aligned}\]\(f(S)\) 是容易算的，指定需要匹配的串后如果有冲突为 \(0\)，否则为 \(26^c\)，\(c\) 是所有串的该位置都是 ? 的位置数。
\(O(n|s|)\) 暴力算 \(f(S)\)，时间复杂度 \(O(2^nn|s|)\)。
接下来是经典的错排问题。令 \(F(n)\) 表示长度为 \(n\) 的错排数，我们置条件集合为 \(\{a_1=1,a_2=2,\dots,a_n=n\}\)，元素即为 \(n!\) 个不同的排列，那么不满足任何条件的元素向答案贡献 \(1\)，否则贡献 \(0\)，就可以直接套用上面的方法。
\[\begin{aligned} F(n)&=\sum_{S\subseteq U}(-1)^{|S|}f(S)\\ \end{aligned}\]我们尝试枚举这些条件，我们发现至少满足 \(k\) 个条件的元素数即至少有 \(k\) 个位置没有错排的排列数为
\[\binom{n}{k}(n-k)! \]即选 \(k\) 个位置不错排，剩下位置任意。
然而这个东西就等同于
\[\sum_{|S|=k}f(S) \]故我们可以根据这些条件集合大小枚举它们
\[\begin{aligned} F(n)&=\sum_{S\subseteq U}(-1)^{|S|}f(S)\\ &=\sum_{i=0}^n\sum_{|S|=i}(-1)^{i}f(S)\\ &=\sum_{i=0}^n(-1)^{i}\sum_{|S|=i}f(S)\\ &=\sum_{i=0}^n(-1)^{i}\binom{n}{i}(n-i)! \end{aligned}\] 标签：sum,元素,容斥,条件,binom,aligned,subseteq From： https://www.cnblogs.com/yukari1735/p/16913859.html