【UOJ #50】链式反应

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$ ,所以这玩意算了。