本题的 O(nlogn) 做法

EntropyIncreaser 2019-08-11 0:45:59 2019-08-11 0:50:31

首先我们定义这样一个东西: \operatorname{MSET} [f(z)] = \prod_n (1 - z^n)^{-f_n} ,那么这个题中我们假设 OGF 是 T(z) = \sum_n t_{n+1}z^n ,那么不难得到一个方程

T(z) = \operatorname{MSET} (\operatorname{MSET} zT - 1)

接下来就是要注意到 \operatorname{MSET} 是可以有更加有用的表示的,读者不难自行验证(事实上这在解析组合中被称作 Pólya 指数):

\operatorname{MSET} f = \exp \left( \sum_{k\ge 1} \frac{f(z^k)}k \right)

接下来我们可以消去所有 f(z^k), k\ge 2 了,注意到我们在进行倍增的时候,由于已知前 \frac n2 项欲求前 n 项,所有 f(z^k), k\ge 2 的地方已经被完全确定了,也就是我们可以把原来的方程在倍增求解时等价为

T(z) = B(z)\exp \left(A(z) \mathrm{e}^{zT(z)} - 1\right)

其中 A(z) = \exp \left( \sum_{k\ge 2} \frac{f(z^k)}k \right), B(z) = \exp \left( \sum_{k\ge 2} \frac{A(z^k)\mathrm e^{z^kT(z^k)} - 1}k \right) 可以通过 \Theta(n\log n) 的时间计算。

考虑求导,我们只需求解微分方程

T'(z) = \frac{T(z)\left( B'(z) + \mathrm{e}^{zT(z)}B(z)(A'(z) + A(z)T(z)) \right)}{B(z)- zT(z)A(z)B(z)\mathrm e^{zT(z)}}

解任意的一阶微分方程已是一个经典问题,综上所述,本题可以以 \Theta(n\log n) 的时间解出。

共 2 条回复

tiger0132

EI tql!

NaCly_Fish

EI tql!