P4492 [HAOI2018] 苹果树
NaCly_Fish
·
·
个人记录
题目链接
考虑从朴素的 DP 来导出更优的 \Theta(n) 解法。面对这样一个递推：
f_{i,j}=j\times f_{i-1,j-1}+(i-j-1)\times f_{i-1,j}+[j=1]i!
根据解迭代列的一些经验，自然是考虑设 F_i(x) 为 \{ f_{i,j}\}_{j=0}^i 的生成函数，就表示为：
F_i(x)=(x^2-x)F_{i-1}'(x)+(i-1+x)F_{i-1}(x)+i!x
注意，我们并不需要实际算出 F_n(x) 的系数，答案只是
\sum_{j=1}^nf_{n,j}\times j(n-j)=(n-1)F_n'(1)-F_n''(1)
接下来的做法用到了递推式中非常强的一个性质，请看：
F_i(1)=iF_{i-1}(1)+i!
发现了吧：F_i(1) 的计算不依赖于任意 F_t'(1)。而对于高阶的导数值，计算也不依赖于更高阶的（这是因为 F_{i-1}'(x) 这一项具有系数 (x^2-x)，每次求导后含有高阶导的那一项还会带着此系数，这就导致代入 x=1 后此项被消去 ）。于是我们只需要对等式两边求导，就可以直接找到递推式：
F_i'(1)=(i+1)F_{i-1}'(1)+F_{i-1}(1)+i!
F_i''(1)=4F_{i-1}'(1)+(i+2)F_{i-1}''(1)
有显然的边界值 F_1(1)=F_1'(1)=1，F_1''(1)=0。直接计算的时间复杂度就是 \Theta(n) 的。比较有意思的是，不同于一般用到的整式递推，这里是不需要求逆元的。