一句话题意，给定 \(n\) , \(m\) ，求 (\(1\),\(2\)) 到 (\(n-1\),\(m\)) 和 (\(2\),\(1\)) 到 (\(n\),\(m-1\)) 的不相交路径方案数。
考虑使用 \(LGV\) 引理解题。
（虽然可以自己推）。
\(LGV\) 引理的定义（来自 \(OI-wiki\)）为
\(\omega(P)\) 表示一条路径上的边权之积（统计路径个数时可以全部赋为1）
\(e(A,B)\) 表示从 \(A\) 到 \(B\) 的所有路径的 \(\omega(P)\) 之和。
\(N(\sigma(S))\) 表示排列 \(\sigma(S)\) 的逆序对数量
\(M= \begin{bmatrix}e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_n)\\e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n)\\ \vdots&\vdots&\ddots&\vdots\\ e(A_n,B_1)&e(A_n,B_2)&\cdots&e(A_n,B_n)\end{bmatrix}\)
\(\det(M)=\sum\limits_{S:A\rightarrow B}(-1)^{N(\sigma(S))}\prod\limits_{i=1}^n\omega(S_i)\)
知道了这些，我们就可以来做这道题了（
根据 \(LGV\) 引理可得，本题答案为
\(e((1,2),(n-1,m))\) \(\times\) \(e((2,1),(n,m-1)-e((1,2),(n,m-1))\) \(\times\) \(e((2,1),(n-1,m))\)
#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
using namespace std;
template <typename T> void read(T &n){ bool f = 1; char ch = getchar(); n = 0; for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 0; for (; isdigit(ch); ch = getchar()) n = (n << 1) + (n << 3) + (ch ^ 48); if (f == 0) n = -n;}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}
const int N = 3010;
int n, m;
int f[N][N];
char ch[N][N];
bool a[N][N];
const int mod = 1e9 + 7;
inline void DP() {
U(i, 1, n) U(j, 1, m) if (a[i][j]) (f[i][j] += (f[i][j - 1] + f[i - 1][j])) %= mod; else f[i][j] = 0;
// cerr << i << " " << j << " " << f[i][j] << "\n";
}
int main(){
//FO("");
read(n), read(m);
U(i, 1, n) {
scanf("%s", ch[i] + 1);
U(j, 1, m) if (ch[i][j] == '#') a[i][j] = 0; else a[i][j] = 1;
}
f[1][2] = 1;
DP();
LL res1 = f[n - 1][m], res2 = f[n][m - 1];
memset(f, 0, sizeof f);
f[2][1] = 1;
DP();
res1 = res1 * f[n][m - 1] % mod, res2 = res2 * f[n - 1][m] % mod;
// cerr << f[n][m - 1] << " " << res2 << "\n";
writeln((res1 - res2 + mod) % mod);
return 0;
}
原文地址：http://www.cnblogs.com/SouthernWay/p/16829348.html
