#50. 【UR #3】链式反应（动态规划/生成函数/分治NTT/解微分方程）

链式反应（动态规划/生成函数/分治NTT/解微分方程）"/>

#50. 【UR #3】链式反应（动态规划/生成函数/分治NTT/解微分方程）

#50. 【UR #3】链式反应

.html
对于一个n个节点的树，编号从1到n，要求每个点的编号小于儿子，并且有两类点，蓝点没有儿子，每个红点要么连接两个红点和若干蓝点，蓝点儿子的数量属于集合A，要么没有儿子。求解树的个数。

我们考虑dp， d p [ i ] dp[i] dp[i]表示i个点的树的答案，然后有
发现这是一个背包的形式，所以我们可以考虑利用生成函数求解。
f ( x ) = ∑ i = 1 n f [ i ] i ! x i , A ( x ) = ∑ i ∈ A x i i ! f(x)=\sum_{i=1}^n\frac{f[i]}{i!}x^i,A(x)=\sum_{i\in{A}}\frac{x^i}{i!} f(x)=∑i=1n​i!f[i]​xi,A(x)=∑i∈A​i!xi​
然后我们可以推出
f ′ = 1 2 A f 2 + 1 f'=\frac{1}{2}Af^2+1 f′=21​Af2+1
多项式的次数代表的就是所有儿子大小之和，所以最后补充的1就代表没有儿子的单独一个点。

然后现在我们已经可以进行分治NTT求解了，但是总的复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)

考虑进一步求解这个式子，本质上需要我们求解一个微分方程，那么首先我们利用牛顿迭代得到
f ′ = g ( f ) = g ( f 0 ) + 1 2 g ′ ( f 0 ) ( f − f 0 ) = g ( f 0 ) + 1 2 g ′ ( f 0 ) f − 1 2 g ′ ( f 0 ) f 0 f ′ − 1 2 g ′ ( f 0 ) f = g ( f 0 ) − 1 2 g ′ ( f 0 ) f 0 f'=g(f) \\=g(f_0)+\frac{1}{2}g'(f_0)(f-f_0) \\=g(f_0)+\frac{1}{2}g'(f_0)f-\frac{1}{2}g'(f_0)f_0 \\f'-\frac{1}{2}g'(f_0)f=g(f_0)-\frac{1}{2}g'(f_0)f_0 f′=g(f)=g(f0​)+21​g′(f0​)(f−f0​)=g(f0​)+21​g′(f0​)f−21​g′(f0​)f0​f′−21​g′(f0​)f=g(f0​)−21​g′(f0​)f0​
现在我们考虑构造将左边变为一个比较好的形式，发现是一个 f ′ + k f f'+kf f′+kf的形式，那么我们可以向 ( g f ) ′ (gf)' (gf)′的方向构造，考虑乘以一个 r r r.
r f ′ + r k f = ( r f ) ′ = r ′ f + r f ′ rf'+rkf=(rf)'=r'f+rf' rf′+rkf=(rf)′=r′f+rf′
那么我们对于r的限制就是
r k = r ′ rk=r' rk=r′
那么这是一个固定的形式
r = e ∫ k d t r = e ∫ − 1 2 g ′ ( f 0 ) d t r=e^{\int{k}\space dt}\\ r=e^{\int{-\frac{1}{2}g'(f_0)} \space dt} r=e∫k dtr=e∫−21​g′(f0​) dt
这样子我们就可以得到
f = ∫ [ g ( f 0 ) − 1 2 g ′ ( f 0 ) f 0 ] r d x r f=\frac{\int[g(f_0)-\frac{1}{2}g'(f_0)f_0]r \space dx}{r} f=r∫[g(f0​)−21​g′(f0​)f0​]r dx​
那么利用牛顿迭代的方法我们成功在 O ( n l o g n ) O(nlogn) O(nlogn)的时间内解决了这个问题。虽然常数巨大跑不过分治NTT。