P3673

· · 题解

搬运一下题解。

记 n=\#1, m=\#0。

先来考虑如何判断是否有解。
对于给定的 a_1,\dots,a_N，连边 i \to a_i，这显然恰会构成内向基环树森林。
若 b_i=1，则要求 i 与 a_i 的真值相同。否则，要求 i 与 a_i 的真值相异。
对于其中一棵内向基环树，注意到内向树部分的限制是很弱的。我们只需要确定环上的所有真值，而树上只需直接推出。
而容易发现环上有解，当且仅当其中恰有偶数个 0，且恰有两个解。

我们用二元 EGF 刻画这个结构。显然，环的 EGF 为

\sum_{k\ge 1} (k-1)! \sum_{j\ge 0} \frac{x^j y^{k-j}}{j!(k-j)!} = \ln\frac1{1-x-y}

而含有偶数个 y 的环的 EGF，可以通过 \frac{1+(-1)^k}2 = [2 \mid k] 得到

\frac12\left(\ln\frac1{1-x-y} + \ln\frac1{1-x+y}\right) = \frac12 \ln\frac1{(1-x)^2-y^2}

而有根树的 EGF 可以直接以复合方程 T(x, y) = (x+y)\mathrm e^{T(x, y)} 刻画。
从而基环树就是环与有根树的复合

\sqrt{\frac1{(1-x\mathrm e^{T(x, y)})^2-(y\mathrm e^{T(x,y)})^2}}

我们欲提取 n! m! [x^n y^m]。

作换元 x\mapsto s, y\mapsto st，有

=[s^{n+m} t^m] \sqrt{\frac1{(1-s\mathrm e^{T(s,st)})^2-(st\mathrm e^{T(s,st)})^2}}

注意到 T(s, st) = s(1+t) \mathrm e^{T(st, t)}，即 s \mathrm e^{T(s, st)} = \frac{T(s, st)}{1+t}，就有

\begin{aligned} &=[s^{n+m} t^m] \sqrt{\frac1{\left(1-\frac{T(s, st)}{1+t}\right)^2-\left(t\frac{T(s, st)}{1+t}\right)^2}} \\ &=[s^{n+m} t^m] \sqrt{\frac{1+t}{1+t-2T(s, st)+(1-t)T^2(s, st)}} \\ &=[s^{n+m} t^m] \sqrt{\frac{1+t}{1+t-2s+(1-t)s^2}} \cdot \left(\frac{s\mathrm e^{-s}}{1+t}\right)' \cdot \left(\frac{s(1+t)}{s\mathrm e^{-s}}\right)^{n+m+1}\\ &=[s^{n+m} t^m] [1+t-2s+(1-t)s^2]^{-\frac12} (1+t)^{n+m+\frac12} (1-s)\mathrm e^{(n+m)s} \\ &=[s^{n+m} t^m] [(1-s)^2+t(1-s^2)]^{-\frac12} (1+t)^{n+m+\frac12} (1-s)\mathrm e^{(n+m)s} \\ &=[s^{n+m} t^m] \left(1+t\frac{1+s}{1-s}\right)^{-\frac12} (1+t)^{n+m+\frac12} \mathrm e^{(n+m)s} \\ &=[s^{n+m}] \mathrm e^{(n+m)s} \sum_{k\ge 0} \binom{-\frac12}k \binom{n+m+\frac12}{m-k} \left(\frac{1+s}{1-s}\right)^k \\ &=[s^{n+m}] \mathrm e^{(n+m)s} \binom{n+m+\frac12}m \cdot {}_2F_1\left(\frac12,-m;n+\frac32;\frac{1+s}{1-s}\right) \\ \end{aligned}

根据 EI 的结果，整个式子是 D-Finite 的。从而我们可以做到 O(N) 甚至 O(\sqrt N \log N)。

记 f_k = [s^k] {}_2F_1\left(\frac12,-m;n+\frac32;\frac{1+s}{1-s}\right)，此处给出 f_k 的一个整式递推式：

\begin{aligned} (k-n-m-1)k f_k \\ -(k-2n-3)(k-1) f_{k-1} \\ -(k+n-m)(k-2) f_{k-2} \\ +(k-2)(k-3) f_{k-3} \\ -mf_{k-1} &= 0 \end{aligned}

读者可以据此得到 O(N) 解法。

也存在等价的 Prufer 序列做法，读者自证不难。