[集训队作业2018]普通的计数题

这个题做了好几天,主要原因是我不太懂怎么解微分方程。
首先暴力dp就是$O(n^5)$的,显然不靠谱,然后可以发现如果把一个位置x向消掉它的那个1的位置连一条边,要使答案合法,整张图一定是棵树。
为了方便起见,我们不妨只做根的编号是1的情况。然后我们可以发现现在的dp方程可以表示成生成函数的方程。
设根编号为1的方案的指数生成函数为$F(x)$,即$n! \lbrack x^n \rbrack F(x)=$n次操作后只剩一个1的方案数,然后$G_a(x)$和$G_b(x)$分别为A和B的指数生成函数。
那么有:$F'(x)=G_a(x)(e^{F(x)}-1)+G_b(x)$
然后这个东西我不知道怎么办了,直接解微分方程很难解出来,然后自然而然想到用类似牛顿迭代的方法倍增。
设$F_t(x)=F(x) \mod x^{(2^t)}$
那么$Ga(x)e^{F_t(x)}+Gb(x)-Ga(x)\equiv F'(x) (\mod x^{(2^t)})$
我们可以发现直接用牛顿迭代是不行的,因为按$F_{t+1}(x)=F_t(x)-\frac{G(F_t(x))}{G'(F_t(x))}$算的话会发现$F'(x)$无法用$F_t(x)$线性表示。
我自己实在不会,然后face不要地看了题解。
大致思路说一下:首先将$e^{F(x)}$这一项化掉,然后使用公式$\int u(x)v'(x)+u'(x)v(x)dx=u(x)v(x)+C$将$F'(x)$全部变为$F(x)$,然后就可以直接求解了。
首先可以发现,这个$F'(x)$非常烦,我们可以先去掉。设$H(x)=G_ae^{x}+G_b-G_a$(这样写看得清楚一点)。
令$H(x)$在$F_t(x)$处泰勒展开,得:
$H(x)=G_ae^{F_t}+G_b-G_a+\displaystyle\sum_{i=1}^{\infty} \frac{G_ae^{F_t}}{i!}(x-F_t)^i$
那么有$H(F)=G_ae^{F_t}+G_b-G_a+\displaystyle\sum_{i=1}^{\infty} \frac{G_ae^{F_t}}{i!}(F-F_t)^i$
那么有:
$F’\equiv G_ae^{F_t}+G_b-G_a+G_ae^{F_t} (F-F_t) (\mod 2^{(2^{t+1})}$
我们把和$F(x)$有关的放到左边:
$F'(x)-G_a(x)e^{F_t(x)}F(x)\equiv G_a(x)e^{F_t(x)}+G_b(x)-G_a(x)-G_a(x)e^{F_t(x)}F_t(x)$
就是说我们要构造一个函数v,使得,$v'(x)=-v(x)G_a(x)e^{F_t(x)}$
这个是一个基本的微分方程,是$\frac{dy}{dx}+yP(x)=0$的形式,解出来的结果是$y=\pm e^{-\int p(x)dx+C}$
在这里不妨令$v(x)=e^{-\int G_a(x)e^{F_t(x)} dx}$。
那么原式就变成了:
$v(x)F'(x)+v'(x)F(x)\equiv v(x)(G_a(x)e^{F_t(x)}(1-F_t(x))+G_b(x)-G_a(x))$
那么:
$F(x)\equiv \frac{1}{v(x)} \int v(x)(G_a(x)e^{F_t(x)}(1-F_t(x))+G_b(x)-G_a(x)) dx(\mod 2^{(2^{t+1})})$
好了,做完了,倍增+一堆多项式操作,时间复杂度一个log,常数巨大。
代码:

Tagged with:

发表评论