ZROJ 25noip10连测day6

$T3$ /原/ AT_code_festival_2017_quala_e

$/count/$ “不同的被赋予姿态的情况”

那可以直接考虑合法的最终局面的结构

$/only/$ “$L$” $and$ “$U$”，$/$设$/$ $\sum L_i = A,\sum U_i = B$

在“考虑最终局面”的意义下，相当于在钦定同向 $n \rightarrow 1,m \rightarrow 1$ 的顺序的意义下考虑方案数

发现只与朝向不同的人的相对顺序有关，也就是要求朝向不同的人的相对行走顺序的方案数

相当于有 $A+B$ 个时间点，给每个 $L$ 人和 $U$ 人都安排一个时间点

也可以视为把 $B$ 个 $U$ 插入到 $A$ 个 $L$ 的序列中的组合方案数

所以这个 $A$ 性质的答案就是 $\tbinom{A+B}{A,B}$

$/only/$ “$L$”$and$“$U$”$and$“$D$”,$/$设$/$ $C = \sum D_i,B,A$

考虑有 $L$ 成为贯通左右的分割线的情况，相当于分割为两个 $A$ 性质的子问题

分割线可能不止一条，所以我们钦定最靠上的分割线为统计答案的位置, 同时也钦定了上半部分的最后一步是 $U$ 走的

这里有一个经典结论如下：

从格路计数的意义下考虑这个式子比较清晰

$\tbinom{A+B+C+1}{A}$ 表示从 $\small (0,0)$ 走到 $\small (A,B+C+1)$ 的方案数

我们考虑在 $\small y=B+1$ 的位置画一条分割线，枚举碰到这条分割线时为 $\small (B+1,i)$,即为左边的式子

考虑有 $U$ $or$ $D$ 先一步成为贯通上下的分割线的情况，考虑枚举最左边一条分割线，发现左半边可以划归到先前的讨论中，右半边相当于乘上一个二的幂次

$/all/$ “$L$”$and$“$R$”$and$“$U$”$and$“$D$

第一条线一定会划分出上下或左右两个部分，接下来的推导是容易的