BZOJ #2863. Angry Führer

19/05/2023 /

Original link: https://www.shuizilong.com/house/archives/bzoj-2863-%E6%84%A4%E6%80%92%E7%9A%84%E5%85%83%E9%A6% 96/

set up f_{i,j} It means that there are exactly j schemes whose in-degree is 0, there are:

(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*}

The complexity is O(n3), we can use the prefix and + redundancy to optimize the enumeration in the inner layer, there are:

(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*}

Here, Newton’s binomial expansion is used, (1+x)^n, and x = -1 is substituted.

This article is reproduced from: https://www.shuizilong.com/house/archives/bzoj-2863-%E6%84%A4%E6%80%92%E7%9A%84%E5%85%83%E9%A6% 96/
This site is only for collection, and the copyright belongs to the original author.