【UOJ #50】链式反应

zhoutb2333 · 2019-01-16 08:26:39 · 个人记录

记一下...

首先设 \large f(i) 为长度为 i 的答案。

不难推出 \large i \ge2 时 \large f(i)= \frac{1}{2} \sum \limits _{t \in A} \binom{i-1}{t} \sum \limits _{j=1}^{i-1-t} \binom{i-1-t}{j} * f(j) * f(i-1-t-j) 。

那么令 \large F(x) 为 \large \{ f \} 的 \tt EGF ，令 \large G(x) = \sum \limits _{i \ge 0} \frac{[i \in A]x^i}{i!} 的话，不难推出 \large F = \frac{1}{2} \int G * F^2 dx + x ，也就是 \large \frac{1}{2} G*F^2 - F'+1 = 0 。

考虑解决一类多项式微分方程：形如 \large \frac{dF_{2n}}{dx} \equiv H(F_{2n}) \pmod{x^{2n}} 。

首先递归解决 \large \frac{dF_n}{dx} \equiv H(F_n) \pmod{x^n} 。

然后对 \large H 在 \large F_n 处泰勒展开并模掉二次及以上项（实际上过程与多项式牛顿迭代类似），得到 \large \frac{dF_{2n}}{dx} \equiv H(F_n) + H'(F_n)*(F_{2n}-F_n) \pmod{x^{2n}} 。

移项得 \large \frac{dF_{2n}}{dx} \equiv H(F_n)-H'(F_n)* F_n + H'(F_n)*F_{2n} \pmod{x^{2n}} 。

我们要把等式右边的未知项去掉，一种解决方法是寻找一个 \large Q(x) ，并使 \large \frac{d(F_{2n}Q)}{dx} = Q * \frac{dF_{2n}}{dx} - Q*H'(F_n)*F_{2n} 。这样的话我们就可以等式两边同时乘以 \large Q(x) ，化为 \large \frac{d(F_{2n}Q)}{dx} \equiv Q(H(F_n)-H'(F_n)*F_n) \pmod{x^{2n}} ，这样的话我们把左边所出来，积分，再除以 \large Q 就是 \large F_{2n} 了。

现在解 \large \frac{d(F_{2n}Q)}{dx} = Q * \frac{dF_{2n}}{dx} - Q*H'(F_n)*F_{2n} ，移项得 \large \frac{dQ}{dx} = - Q * H'(F_n) 。 这时候就可以使用可分离变量型微分方程的解法了。解得 \large Q=e^{-\int H'(F_n)dx} 。

那么显然打不过分治 \tt NTT ，所以这玩意算了。