https://www.becoder.com.cn/contest/5400
「BZOJ2863」愤怒的元首
题目就是求 \(n\) 个点 DAG 的数量。
设 \(dp_i\) 表示 \(i\) 个点的 DAG 数量。
首先 DAG 一定存在出度为 \(0\) 的点，其次删去出度为 \(0\) 的点，仍构成一个 DAG。
所以我们可以枚举删去的数量，从而划分子问题。
\(g(n)\) 表示从 \(N\) 个不同元素 钦定/选至少 \(n\) 个元素形成特定结构的方案数；
\(f(n)\) 表示 恰好 使用 \(n\) 个不同元素（且这 \(n\) 个元素包含所有被钦定的）形成特定结构的总方案数。
具体地，\(dp_i=\sum\limits_{j=1}^i{i\choose j}dp_{i-j}2^{j(i-j)}\)
但是这样显然不对，因为后面算的实际上是至少，而我们需要的是恰好，即 \(g(j)={i\choose j}dp_{i-j}2^{j(i-j)}\)。
于是二项式反演一下：
\[\begin{aligned} dp_i&=\sum_{j=1}^if(j)\\ &=\sum_{j=1}^i\sum_{k=j}^{i}{k\choose j}(-1)^{k-j} g(k)\\ &=\sum_{j=1}^i\sum_{k=j}^{i}{k\choose j}(-1)^{k-j}{i\choose k}dp_{i-k}2^{k(i-k)}\\ &=\sum_{k=1}^i{i\choose k}dp_{i-k}2^{k(i-k)}\sum_{j=1}^{k}{k\choose j}(-1)^{k-j}1^j&【\text{换求和顺序}】\\ &=\sum_{k=1}^i{i\choose k}dp_{i-k}2^{k(i-k)}(0-(-1)^k)&【\text{二项式定理(需要补 0 次项)}】\\ &=\sum_{k=1}^i(-1)^{k-1}{i\choose k}dp_{i-k}2^{k(i-k)} \end{aligned} \]或者直接考虑容斥（再一次体现了容斥和二项式定理本质是相同的。
就是上面的最后一个式子。
标签：Set,sum,容斥,反演,DAG,choose,二项式,dp From： https://www.cnblogs.com/CloudWings/p/18310991