Monotonic Matrix (LVG引理, 路径不相交)

发布时间 2023-06-13 16:53:24作者: VxiaohuanV

引入

给定一个 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定理即可