RT

是这样的：我看到此题目后尝试着推了一段时间，先是成功推出了 $O(n)$ 的递推式：

$d_i=4\times d_{i-1}-2\times C_{i-1}$

（具体过程较为复杂但是相对自然，我之后可能写一篇题解记录）

然后又卡住了。

最后也是一眼丁真猜到结论，并成功用上面的递推式证明了该结论（证明不难）。

然后我观察了题解区，大多是先猜出结论，再使用组合意义论证它。

我承认这当然严谨，但是太考察注意力了。

题解区有两篇 GF+求导 做法，但是也略有点这种感觉，@pp_orange 也提出了这一点。

楼主太菜，想知道有没有什么更加自然的方法。