引入
给定一个 n×m 的网格图,两个点从左下角出发,只能向上或者向右走,最后到右上角结束,求有多少种可能的方案,使得两个点的路径在除开起点和终点外的任意点不相交?
由于交换路径过后算同一种方案,我们就可以除开起点和终点,转换成A点从(1,2)出发到(m-1,n),B点从(2,1)出发到(m,n-1),再来统计不相交的路径方案数。
1.统计A、B独立地从各自起点走到各自终点的路径方案数,答案加上两者的乘积。
2.交换A、B的终点,再次统计方案数,答案减去两者乘积。
题目大意:
一个矩阵由012三个数字组成,这个矩阵从左到右,从上到下,都是不递减的
思路:
- 转化为2个路径, 把矩阵分成 0 1 2 ,3个部分
- 这个路径是 坐上到右下的
- 然后 这个线可以相交的, 将其中一个线, 向左向下 平移一下即可
- 然后2个点在矩阵中的路径 是可以通过组合数求出来的
- 于是直接套 LVG定理即可