为什么这么典的套路我现在才第一次见到呢？
一道题
有 $n$ 天，每天可以购入一个物品或者出售一个物品或者什么都不做，物品的价格未知，是一个 $1$ 或 $2$ 的数，对于每个 $k$ 求出有多少种物品价格方案使得最大收益为 $k$ ，$n\leq 10^6$。
做法
首先进行一些转化，令左括号的个数为 $x$，当 $x\leq \frac{n}{2}$ 时，左括号看做 $1$，右括号看做 $-1$。然后令最小前缀和为 $y$，那么答案就是 $n-x-y$。当 $x>\frac{n}{2}$ 时完全对称，下面全部令 $x\leq \frac{n}{2}$。
将答案 $=k$ 转化为 $x\geq k$，然后容斥回去。下面我们的问题等价于从 $(0,0)$ 开始走路，每次可以走 $(1,1)$ 或 $(1,-1)$，求不经过 $y=k+x-n-1$ 到达 $(n,2x-n)$ 的方案数。
下面就是这个套路，首先如果没有限制，方案数就是 $\binom{n}{x}$，我们考虑计算经过这条线的方案数减去，考虑怎么钦定经过这条线，我们取起点 $(0,0)$ 关于 $y=k+x-n-1$ 的对称点，那么方案数就是从对称点出发到达终点的方案数。因为从对称点到达终点显然必须经过这条线，因为他们在这条线的两侧。然后考虑将第一次经过这条线之前的部分关于这条线对称回去，显然是和原问题等价的。对于本题，这部分代价就是 $\binom{n}{k-1}$。
然后前缀和优化就做完了。