20210619 省队互测

· · 个人记录

题意: 有 n 句话，第 i 句话形如“第 f_i 句话是真/假的”. 现在 f 已经找不到了，只剩下后面这个真假性了. 你需要求出有多少种序列 f 满足存在一个合法方案. 对 998244353 取模（原题是对 2^{32} 取模）.

出题人给出了一个 \Theta(n^4) 的做法，我们来把它优化到 \Theta(\sqrt{n}\log n)

由于每个点出度为 1，所以图最终形成一个基环树森林. 接下来考虑限制，如果有边 a\to b，那么 a 的真值和 b 的真值不同当且仅当 a 说的是假话. 于是这相当于是限制了 a 与 b 的异或和，那么只要环上的异或和为 0 我们就总能构造出一种方案.

现在问题就是，我们有 n 个说真话的和 m 个说假话的，求有标号基环森林的数量，满足每个环上有偶数个说假话的. 记 x 为真话的占位元，y 为假话的占位元，我们考虑答案的生成函数

\sum_{i\geq 0}\sum_{j\geq 0}f_{i,j}\frac{x^i}{i!}\frac{y^j}{j!}

先考虑一个环的 GF，如果不考虑有偶数个 y 的限制，那么直接枚举环的点数就有

\sum_{k\geq 1}\frac{(x+y)^k}{k}=\ln\frac{1}{1-(x+y)}

考虑偶数个 y 的限制，利用 [i\bmod 2=0]=\dfrac{1^i+(-1)^i}{2}，我们就有

R(x,y)=\frac{1}{2}\left(\ln\frac{1}{1-(x+y)}+\ln\frac{1}{1-(x-y)}\right)

现在考虑树，我们只需要把环上每个点扩充为一棵树即可，因此基环树的 GF 就是

R(xe^T,ye^T)

其中 T 满足 T=(x+y)e^T，即有标号树的 GF

我们要求的是基环森林，也即

\exp(R(xe^T,ye^T))

先考虑 \exp(R(x,y))，这就是

\sqrt{\frac{1}{(1-x)^2-y^2}}

我场上写的大概是直接将其展开来计算得到 h(x,y)，然后 \Theta(nm) 计算 n!m![x^ny^m]h(xe^T,ye^T). 但这样有个很诡异的问题是 h 的展开式中分母有一个 4^i 项，我并不会消去，但实践表明考虑后面的计算时这个分母会和分子完全抵消，也就是每一项都是整数，原理暂时不明 整个 998244353 不好吗

当然实际上我们可以直接考虑整体的计算，先做换元 y\leftarrow tx,x\leftarrow t，那么我们要算的东西形如

[t^nx^m]\sqrt{\frac{1}{(1-te^T)^2-(txe^T)^2}}

其中 T 满足 T=t(1+x)e^T，也就是 te^T=\dfrac{T}{1+x}，带入得到

[t^nx^m]\sqrt{\frac{1+x}{1+x-2T+(1-x)T^2}}

接下来不难想到对 T 拉格朗日反演，T 满足复合方程 \dfrac{T}{(1+x)e^T}=t，这样上式就等于

[t^nx^m]\sqrt{\frac{1+x}{1+x-2t+(1-x)t^2}}\left(\frac{t}{(1+x)e^t}\right)'(1+x)^{n+1}e^{(n+1)t}

把求导展开之后我们要求的东西形如

[t^nx^m]\left(1-2t+t^2-x(t^2-1)\right)^{-1/2}(1+x)^re^{kt}

按 x 展开根式就是

\frac{e^{kt}}{1-t}\sum_{i=0}^m\binom{-1/2}{i}\binom{r}{m-i}\left(\frac{1+t}{1-t}\right)^i

由于

\sum_{i\geq 0}\binom{-1/2}{i}\binom{r}{m-i}x^i

是超几何函数

\binom{r}{m}F\left(\left.\begin{matrix}1/2,-m\\r-m+1\end{matrix}\right| x\right)

其满足微分方程

(\operatorname{\vartheta}+\frac{1}{2})(\operatorname{\vartheta}-m)F=\operatorname{D}(\operatorname{\vartheta}+r-m)F

所以上面整个式子微分有限，存在整式递推