牛客网暑期ACM多校训练营（第一场）A Monotonic Matrix(详解)

A Monotonic Matrix

先备知识

LGV 算法 (Lindström–Gessel–Viennot lemma)[LGV 算法就是求从 $\{a_1,a_2,...a_n\}${a1​,a2​,...an​} 到 $\{b_1,b_2,...b_n\}${b1​,b2​,...bn​} 的不交路径的条数

求以上矩阵的行列式，其中 e(a,b) 是从a到b的方法数，带入求行列式即可得到(a1,a2,…an) 到 (b1,b2,…bn) 的所有不相交路径的种数

思路

考虑01和12的分界线
是(n, 0)到(0，m)的两条不相交（可重合）路径
分界线以及分界线以上的点是一种，分界线下是一种
平移其中一条变成(n-1, -1)到(-1，m-1);
变成
起点 $a_1,a_2=(n,0),(n-1,-1)$a1​,a2​=(n,0),(n−1,−1)
终点 $b_1,b_2=(0,m),(-1,m-1)$b1​,b2​=(0,m),(−1,m−1)

然后进行预处理打表前2*n的阶乘和阶乘逆元就行了