theme: seriph
background: flase
class: text-center
highlighter: shiki
lineNumbers: false
info: |
## Slidev Starter Template
Presentation slides for developers.
Learn more at [Sli.dev](https://sli.dev)
drawings:
persist: false
transition: slide-left
title: 生成树
首先我们需要考虑如何找到一个 \((t,B)\) 二元组合法的充要条件，其中 \(t\) 是终点，\(B\) 是每个位置被喂了多少次。
不妨假设最后一步走回了 \(A\)，并且钦定最后一步不给其加上 \(1\)，那么从左往右找到第一个有值的位置，记为 \(x\)，那么一定从 \(x+1\) 走向了 \(x\) \(B_x\) 次，又走回去 \(B_x\) 次，这样会给 \(x\) 和 \(x+1\) 都增加 \(B_x\)，将这个贡献扣除，然后继续。如果过程中出现某个 \(B_x<0\) 则不合法。同时因为移动过程是连续的，因此 \(B\) 中有值的部分也应是连续的。
先不管这个过程是不是很抽象，考虑终点任意的情况，这时我们可以补齐终点到 \(A\) 的那一段，这样子就可以看作是走回 \(A\) 了。
现在我们考虑一个暴力，枚举 \(x,l,r\)，表示终点，走到的最左/最右端点，这样的话，我们考虑对 \(B_x,B_{x+1}\) 同时减去多少计数，这样的话需要满足 \(m\) 在补齐后是偶数，然后插板即可。具体的，不妨令 \(x>A\)，则为 \({\frac{m+x-A}{2}-1\choose r-l-1}\)
有上指标求和公式 \(\sum\limits_{i=0}^{b}{i\choose a}={b+1\choose a+1}\)，可以根据组合意义理解为，枚举第一个选的球在哪里，然后剩下 \(a\) 个在剩下 \(i\) 个中选择。观察到如果分 \(x>A\) 与 \(x<A\) 讨论，则在\(l,r\) 固定的时候，下指标固定，上指标是一段连续的区间，可以直接利用上指标求和公式解决，做到 \(O(n^2)\)。
可以观察到，当 \(x>A\) 的时候，式子只有下半部分和 \(l\) 有关，则这变成组合数前缀和问题，可以用莫队解决，时间复杂度 \(O(n\sqrt n)\)，\(x<A\) 同理。不过这题中左右端点是单调的，所以可能是 \(O(n)\) 的。