万泉部诗人

观察一下题目的形式有无更好的结构？

感觉直接能瞪出来的都是神人了。

一个简单的想法是分治，对于 $n$ 的情形，和两个 $\frac{n}{2}$ 的解，将其拼起来是否合法？

我把 $n=3$ 时的不等关系列了一下。

可以得到一个结论是：假设有两个 $\frac{n}{2}$ 的合法解，那么能拼起来当且仅当差分序列相同。

那么可以考虑一个 dp 是：解决了 $2^i$ 的问题后，当前序列的 $\max,\min$ 分别是 $j,k$ 的方案数是 $f_{i,j,k}$。

枚举一下另一半的开头和自己开头的差，则另一半直接确定，但是要保证数都在值域内，这是要记录 $\max,\min$ 的原因。

这个复杂度上天了，而且状态不得不记很没有前途。

考虑直接计数。

将这个过程抽象成：在一个数轴上有一个初始区间 $[x,x]$，也就是 $n=0$ 时的一个解。每次可以选择：不动（另一半和自己完全一样），左端点向左扩展 $c$ （另一半开头比自己小 $c$ )，右端点向右扩展 $d$（另一半开头比自己大 $c$ )。

考虑终态的区间 $[l,r]$，显然我们只关心区间长度，所以先在值域上选出这个区间。然后枚举到底有几段非 $0$ 的扩展，随后将段分配给向左扩展还是向右扩展。下面的式子需要补上 $z+1$，因为没算完全不扩展的情况。可以得到以下式子：

解题的关键是 $L$ 的枚举不可接受，因而调整枚举顺序。

我们来观察一下最后一个求和。

前者是上指标求和 $z\binom{z}{k}$，后者是下面的形式：

形式很有吸收释放的味道，所以构造 $\binom{i+1}{m+1}=\frac{i+1}{m+1}\binom{i}{m}$

因而

于是形式变为了正常的上指标求和。

带入一下。

方便起见 $k=1$ 单独算。原式就是：

这个玩意看起来很和善，已经可以直接卷了。

能不能再给力一点啊？

最后一个括号之和 $z,k$ 有关，提前。

剩下一个：

没有求和就是一个很常见的恒等式的一半，但是没用。

将组合数拆开：

哇，最后一项就是 $[x^k]e^{2x}=\frac{2^k}{k!}$。

整理一下：

带回去：

完结撒花！

但是为啥别人的这么好推呢？

因为我多枚举了 $0$ 的个数导致多了个 $\sum$。其实直接忽略 $0$ 就好了。