（好久没碰差点忘了，赶快泄个推导
目的是求恰好满足\(k\)个要求的方案数\(P(k)\)。
考虑还是用满足至少\(i\)个条件的式子算，不过要为原来的式子构造容斥系数\(\alpha(j)\)
\[
\sum_{i=0}^{n}\binom{n}{i}\alpha(i)Q(i)
\]
可以考虑\(P(i)?\)被算了几次。
\[
\sum_{i=0}^{n}\binom{n}{i}\alpha(i)Q(i)=\sum_{i=0}^n{P(i)\sum_{j=0}^n\binom{i}{j}\alpha(j)}
\]
目的是强制使得\(P(k)=\sum_{i=0}^n{P(i)\sum_{j=0}^n\binom{i}{j}\alpha(j)}\)成立。
所以容斥系数的效果实际上就是
\[
\sum_{j=0}^n\binom{i}{j}\alpha(j)=[i==k]
\]
发现\(j>i\)时其实没用，变成\(\sum_{j=0}^i\binom{i}{j}\alpha(j)=[i==k]\)
把\(\alpha(i)\)单独丢出来，发现可以\(n^2\)搞出每个容斥系数，即
\[
\alpha(i)=[i==k]-\sum_{j=0}^{i-1}\binom{i}{j}\alpha(j)
\]
恰好满足\(k\)个要求的方案数对应的\(\alpha(i)\)对应的可以取\(\alpha(j)=\binom{j}{k}(-1)^{j-k}\)。
当\(i<k\)时式子始终为\(0\)，当\(i\geq k\)时有
\[
\begin{aligned}
& \sum_{j=0}^i\binom{i}j{}\alpha(j)\= & \sum_{j=0}^i{\binom{i}{j}\binom{j}{k}(-1)^{j-k}}\= & \sum_{j=k}^{i}\binom{i}{j}\binom{j}{k}(-1)^{j-k}\= & \sum_{j=0}^{i-k}{\binom{i}{j+k}\binom{j+k}{k}(-1)^j}\= & \sum_{j=0}^{i-k}\frac{i^{\underline{j+k}}(j+k)^{\underline{k}}}{(j+k)!k!}(-1)^j\= & \sum_{j=0}^{i-k}\frac{i^{\underline{k}}(i-k)^{\underline{j}}(j+k)^{\underline{k}}}{k!(j+k)^{\underline{k}}j!}(-1)^j\= & \binom{i}{k}\sum_{j=0}^{i-k}\frac{(i-k)^{\underline{j}}}{j!}(-1)^j\= & \binom{i}{k}\sum_{j=0}^{i-k}\binom{i-k}{j}(-1)^j\= & [i-k==0]\= & [i==k]
\end{aligned}
\]
实际上丢二项式反演好用（雾
\[
f(n) = \sum_{i = 0}^{n}{g(i)\binom{n}{i}} \Longleftrightarrow g(n) = \sum_{i = 0}^n{(-1)^{n-i}\binom{n}{i}f(i)}
\]
\[
\begin{aligned}
g(n) =& \sum_{i = 0}^n{(-1)^{n-i}\binom{n}{i} \sum_{j = 0}^{i}{g(j) \binom{i}{j}}}\=& \sum_{j = 0}^n{g(j) \sum_{i = j}^{n}{(-1)^{n - i} \binom{n}{i}\binom{i}{j} }}\=& \sum_{j = 0}^n{g(j)\sum_{i = j}^{n}{(-1)^{n - i}\binom{n}{j} \binom{n - j}{i - j}}}\=& \sum_{j = 0}^n{g(j)\binom{n}{j}\sum_{i = j}^{n}{(-1)^{n - i}\binom{n - j}{i - j}}}\=& \sum_{j = 0}^n{g(j)\binom{n}{j}(-1+1)^{n-j}}\=& \binom{n}{n}g(n) \=&g(n)\\end{aligned}
\]
所以这个是正确的。
意义：（先证明再说意义还行
\(f(n)\)一般情况下代表至多满足\(n\)个条件的方案数，对应地，\(g(n)\)表示恰好满足\(n\)个条件的方案数。
当然有时候其实是反过来的，定义\(f(i)\)是至少满足\(i\)个约束的方案数，\(g(n)\)是恰满
足\(n\)个约束的方案数，那么：
\[ g(k)=\sum_{i=k}^n{(-1)^{i-k}\binom{i}{k}f(i)} \]
证明就是一开始提到的构造容斥系数\(\alpha(j)\)那一坨
暴力带回去说是对的不就行了管他咋构造出来的
原文：https://www.cnblogs.com/cjc030205/p/11638086.html