万泉部诗人
Le0Chan
·
·
题解
AT_arc144_d
观察一下题目的形式有无更好的结构？
感觉直接能瞪出来的都是神人了。
一个简单的想法是分治，对于 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，因为没算完全不扩展的情况。可以得到以下式子：
\sum\limits_{L=0}^z\sum\limits_{k=1}^n\sum\limits_{i=0}^k (z-L+1)\binom{L-1}{k-1}\binom{n}{k}\binom{k}{i}
解题的关键是 L 的枚举不可接受，因而调整枚举顺序。
\sum\limits_{k=1}^n\sum\limits_{i=0}^k \binom{n}{k}\binom{k}{i}\sum\limits_{L=0}^z (z-L+1)\binom{L-1}{k-1}
我们来观察一下最后一个求和。
z\sum\limits_{L=0}^z \binom{L-1}{k-1}-\sum\limits_{L=0}^z(L-1)\binom{L-1}{k-1}
前者是上指标求和 z\binom{z}{k}，后者是下面的形式：
\sum\limits_{i=0}^ni\binom{i}{m}
形式很有吸收释放的味道，所以构造
\binom{i+1}{m+1}=\frac{i+1}{m+1}\binom{i}{m}
因而
(m+1)\binom{i+1}{m+1}-\binom{i}{m}=i\binom{i}{m}
于是形式变为了正常的上指标求和。
\sum\limits_{i=0}^ni\binom{i}{m}=(m+1)(\binom{n+2}{m+2}-[m=0])-\binom{n+1}{m+1}
带入一下。
z\binom{z}{k}-\sum\limits_{L=0}^z(L-1)\binom{L-1}{k-1}
z\binom{z}{k}-\sum\limits_{L=0}^{z-1}L\binom{L}{k-1}
z\binom{z}{k}-k(\binom{z+1}{k+1}-[k=1])+\binom{z}{k}
方便起见 k=1 单独算。原式就是：
\sum\limits_{k=2}^n\sum\limits_{i=0}^k \binom{n}{k}\binom{k}{i}((z+1)\binom{z}{k}-k\binom{z+1}{k+1})
这个玩意看起来很和善，已经可以直接卷了。
能不能再给力一点啊？
最后一个括号之和 z,k 有关，提前。
\sum\limits_{k=2}^n((z+1)\binom{z}{k}-k\binom{z+1}{k+1})\sum\limits_{i=0}^k \binom{n}{k}\binom{k}{i}
剩下一个：
\sum\limits_{i=0}^k \binom{n}{k}\binom{k}{i}
没有求和就是一个很常见的恒等式的一半，但是没用。
将组合数拆开：
\sum\limits_{i=0}^k\dfrac{n!k!}{k!(n-k)!i!(k-i)!}
\dfrac{n!}{(n-k)!}\sum\limits_{i=0}^k\dfrac{1}{i!(k-i)!}
哇，最后一项就是 [x^k]e^{2x}=\frac{2^k}{k!}。
整理一下：
\dfrac{n!}{(n-k)!}\frac{2^k}{k!}
带回去：
\sum\limits_{k=2}^n((z+1)\binom{z}{k}-k\binom{z+1}{k+1})\dfrac{n!}{(n-k)!}\frac{2^k}{k!}
\sum\limits_{k=2}^n((z+1)\binom{z}{k}-k\binom{z+1}{k+1})\binom{n}{k}2^k
\sum\limits_{k=2}^n((z+1)\binom{z}{k}-\frac{(z+1)k}{k+1}\binom{z}{k})\binom{n}{k}2^k
\sum\limits_{k=2}^n\binom{z+1}{k+1}\binom{n}{k}2^k
完结撒花！
但是为啥别人的这么好推呢？
因为我多枚举了 0 的个数导致多了个 \sum。其实直接忽略 0 就好了。