某岛

… : "…アッカリ～ン . .. . " .. .

May 19, 2023

BZOJ #2863. 愤怒的元首

设 $f_{i,j}$ 表示恰好有 j 个点入度为 0 的方案，有：

(1) $\begin{align*} f_{i,j} &= \sum_{j=1}^{i} \binom{i}{j} \sum_{k=1}^{i-j} f_{i-j,k} (2^j-1)^k 2^{j(i-j-k)} \end{align*}$

复杂度 O(n3)，我们可以利用前缀和 + 冗斥优化掉里层的枚举，有：

(2) $\begin{align*} f_i &= \sum_{j=1}^{i} (-1)^{j-1} \binom{i}{j} \sum_{k=1}^{i-j} f_{i-j} 2^{j(i-j)} \end{align*}$

这里利用了牛顿二项式展开，(1+x)^n，把 x = -1 代入。

Posted by xiaodao
Category: 日常