标签：出度 2863 limits sum 容斥 binom 元首 dp bzoj
bzoj #2863
- 设 \(dp_i\) 表示 \(i\) 个点的 DAG 个数。发现一个 DAG 删去出度为 \(0\) 的点后显然还是一个 DAG ，因此不妨枚举出度为 \(0\) 的点的个数： \(dp_i = \sum\limits_{j=1}^i dp_{i-j}\binom{i}{j}2^{j(i-j)}\)
- 这么干显然不太对，因为我们不能保证每次删除时都能把图中的所有出度为 \(0\) 的点删完，换言之，我们后面这个式子求的是至少有 \(j\) 个出度为 \(0\) 的点的方案数，而我们想要求恰好，显然容斥原理
- 我们设 \(f_j\) 表示恰好有 \(j\) 个出度为 \(0\) 的点方案数， \(g_i\) 表示至少有 \(j\) 个出度为 \(0\) 的点方案数，根据广义容斥，可以知道：
\[g_i = \sum\limits_{j=i}^{n} \binom{j}{i} f_j \Leftrightarrow
f_i = \sum\limits_{j=i}^{n} (-1)^{j-i} \binom{j}{i} g_j
\]
- 而 \(dp_i = \sum\limits_{j=1}^{i} f_i\) ，因此：
\[\begin{align}
dp_i
&= \sum_{j=1}^{i} f_j \\
&= \sum_{j=1}^{i} \sum_{k=j}^{i} (-1)^{k-j} \binom{k}{j} g_k \\
&= \sum_{j=1}^{i} \sum_{k=j}^{i} (-1)^{k-j} \binom{k}{j} dp_{i-k}\binom{i}{k}2^{k(i-k)} \\
&= \sum_{k=1}^{i} \sum_{j=1}^{k} (-1)^{k-j} \binom{k}{j} dp_{i-k}\binom{i}{k}2^{k(i-k)} \\
&= \sum_{k=1}^{i} \binom{i}{k} 2^{k(i-k)} dp_{i-k} \sum_{j=1}^{k} (-1)^{k-j} \binom{k}{j} \\
&= \sum_{k=1}^{i} \binom{i}{k} 2^{k(i-k)} dp_{i-k} (0-(-1)^j) \\
&= \sum_{k=1}^{i} (-1)^{j+1} \binom{i}{k} 2^{k(i-k)} dp_{i-k} \\
\end{align}
\]
- 还有一种理解思路：根据容斥原理， \(|\cup_{i=1}^n A_i|=\sum_{i=1}^{n} (-1)^{i+1} \sum_S |\cap_{x \in S} A_x|\) ，因此直接容斥就可以
- 最终复杂度 \(O(n)\)
标签：出度,
2863,
limits,
sum,
容斥,
binom,
元首,
dp,
bzoj
From： https://www.cnblogs.com/fox-konata/p/17794552.html