cf348D. Turtles(LGV定理 dp)

题意

题目链接

在\(n \times m\)有坏点的矩形中找出两条从起点到终点的不相交路径的方案数

sol

lindström–gessel–viennot lemma的裸题？

这个定理是说点集\(a = \{a_1, a_2, \dots a_n \}\)到\(b = \{b_1, b_2, \dots b_n \}\)的不相交路径条数等于

\[ \begin{bmatrix} e(a_1, b_1) & e(a_1, b_2) & \dots & e(a_1, b_n) \\ e(a_2, b_1) & e(a_2, b_2) & \dots & e(a_2, b_n) \\ \dots & \dots & \dots & \dots \\ e(a_n, b_1) & e(a_n, b_2) & \dots & e(a_n, b_n) \\ \end{bmatrix} \]

的行列式的值。其中\(e(x, y)\)表示从\(x\)到\(y\)的路径条数

定理的本质还是容斥

回归到本题，我们需要找到两条不相交的路径。注意到任何一对合法的路径一定是一条从\((1, 2)\)出发到\((n - 1, m)\)，另一条从\((2, 1)\)出发到\((n, m - 1)\)

那么选取\(a = \{(1, 2) \ (2, 1)\}, b = \{(n - 1, m) \ (n, m - 1)\}\)

带入到上述定理即可求解

#include<bits/stdc++.h> 
#define pair pair<int, int>
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define int long long 
#define ll long long 
#define pt(x) printf("%d ", x);
#define fin(x) {freopen(#x".in","r",stdin);}
#define fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int maxn = 3001, inf = 1e9 + 10, mod = 1e9 + 7;
const double eps = 1e-9;
void chmax(int &a, int b) {a = (a > b ? a : b);}
void chmin(int &a, int b) {a = (a < b ? a : b);}
int sqr(int x) {return x * x;}
int add(int x, int y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
void add2(int &x, int y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
int mul(int x, int y) {return 1ll * x * y % mod;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int c[maxn][maxn], n, m;
char a[maxn][maxn];
int f(int a, int b, int c, int d) {
    memset(c, 0, sizeof(c));
    for(int i = a; i <= c; i++) 
        for(int j = b; j <= d; j++) 
            if(a[i][j] == '.') {
                if(i == a && j == b) c[i][j] = 1;
                else  c[i][j] = add(c[i - 1][j], c[i][j - 1]);              
            }

    return c[c][d];
}
void solve() {
    n = read(); m = read();
    for(int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
    cout << add(mul(f(1, 2, n - 1, m), f(2, 1, n, m - 1)), -mul(f(1, 2, n, m - 1), f(2, 1, n - 1, m))) << '\n';
}
signed main() {
    for(int t = 1; t; t--, solve());
    return 0;
}