本题解是对洛谷一位巨佬题解的补充说明——要不是太精简我写这么多作甚（划掉）
先概括一下题意：
在一个矩形中，每次从左上角开始只能向下或向右移动一步
按照这样的方式移动至右下角的路径称为合法，记为W.
对于两条路径W1,W2而言，它们第一次移动方向发生变化时，约定向右移动的（不妨设为）W1“大于”W2。
现在要求你将每个格子填上一个数，只能为0或1.
并规定每条路径W的字典序为经过的所有格子顺次排列而成的字符串（详见原题中的样例）
问一共有多少种满足要求的方案。
我们来梳理一下思路：
先明确存在可以高效算出正解的算法，但更显然的一点是：
由于大方格可以划分为若干小方格，易推导出数学/递推公式
不妨从约束条件考虑
1.副对角线从下到上不减
证明是显然的，记一条副对角线上两点为（x,y) (x - a,y + a) x - a >=1 && y + a <= m
若（x,y)小的话，考虑从左上角开始到(x - a,y)之间任意一条路径W。
先令a = 1.令终点为（x,y+1).
从（x - a,y) 经（x,y)与（x - 1,y+1)到终点（x,y+1)的路径不合法
对于a的其他值，归纳法就可以了。
2.对于任意一点（x,y),它与（x-1,y+1)相等的必要不充分条件为在（x-1,y)为右下角的矩形中存在一条副对角线，其上存在两点相邻且相等
不充分显然的，副对角线点两两不等的话出现方向变化时向右的肯定会进入填0的格子，字典序就小了；
不一定使（x,y)(x-1,y+1)相等
必要性的话利用反证法：若以（x-1,y)为右下角的矩形中存在一条副对角线，其上有相邻且相等的两点而（x,y)与（x-1,y+1)不等
那么记副对角线上相邻两点为（a,b)，(a-1,b+1)。从左上角分别向下，右走a步，记为W1,W2，再分别向右，下走b步即可
到达（a,b),(a-1,b+1)。再走相同的步数到达（x,y)与（x-1,y+1)。若这两点不等，则W1,W2不合法
证毕。
然后利用两性质快速爆搜打表即可（甚至直接交程序都能骗得可观分数）
剩余的请移步至洛谷吧QwQ
