题解：P13939 [EC Final 2019] Black and White
P2441M
·
·
题解
将路径视作长度为 n+m 的 \texttt{UR} 序列。若将一对相邻的 \texttt{UR} 交换成 \texttt{RU}，则变化恰好是：由这两步包裹住的格子从路径的右侧变到了左侧。
设这两步分别为第 t,t+1 步，则路径权值的变化量为 (-1)^{t-1}，注意到这和 \texttt{UR} 序列偶数位置上 \texttt{U} 的数量的变化量相同，因此这两个量必然有固定的差值。取一条前 n 步向上走，后 m 步向右走的路径，路径权值为 0，偶数位置上 \texttt{U} 的数量为 \left\lfloor\dfrac n2\right\rfloor，于是差值恰好为 \left\lfloor\dfrac n2\right\rfloor。
问题转化为：求有多少由 n 个 \texttt{U} 和 m 个 \texttt{R} 组成的 \texttt{UR} 序列，满足偶数位置上 \texttt{U} 的数量为 k'=k+\left\lfloor\dfrac n2\right\rfloor。显然答案为
\binom{\left\lfloor(n+m)/2\right\rfloor}{k'}\binom{\left\lceil(n+m)/2\right\rceil}{n-k'}
时间复杂度为 \mathcal{O}(\max(n,m)+T)。