【UOJ #50】链式反应

记一下... 首先设 $\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$ ，所以这玩意算了。