某岛

… : "…アッカリ～ン . .. . " .. .
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: 日常

« | »

  • Archives

    open all | close all