[Codeforces348D] Turtles (DP, LGV引理)

发表于 | 分类于 ， | 评论数： | 阅读次数：

链接：http://codeforces.com/contest/348/problem/D

两只乌龟在棋盘上从(1,1)出发到(n,m)，其中有的地方有障碍物，两只乌龟希望找到有多少对路径，使得他们到(n,m)的路上不相交。

如果我没有做牛客多校，我也不会知道这个冷艳的Lindstrom-Gessel-Viennot引理。今天翻笔记看到了，还记得CF上有一道考这个的，于是来除草。

这东西出题很单一，就是用来计算n对起止点不相交路径组合数的，出题也挺单一，其中的一个trick可能是在拆点这方面，给出公式：

img

其中$e(a_i,b_j)$表示从起点$a_i$到终点$b_j$的路径数，M的行列式的值就是我们要求的不相交路径的组合数了。

关于拆点，一般都是移动到起点附近步长为1的位置，终点也是，具体我不太明白，希望有朝一日能证明出来：)

img

这题的DP方程就很简单了，看代码吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int maxn = 3030;
const LL mod = 1E9+7;
int n, m;
char s[maxn][maxn];
LL f[maxn][maxn];

signed main() {
	// freopen("in", "r", stdin);
	while(~scanf("%d%d",&n,&m)) {
		for(int i = 1; i <= n; i++) {
			scanf("%s", s[i]+1);
		}
		memset(f, 0, sizeof(f));
		if(s[1][2] == '#' || s[2][1] == '#') {
			printf("0\n");
			continue;
		}
		LL a, b, c, d;
		f[1][2] = (s[1][2] != '#');
		for(int i = 1; i <= n; i++) {
			for(int j = 2; j <= m; j++) {
				if(s[i][j] == '#') continue;
				f[i][j] += (f[i-1][j] + f[i][j-1]) % mod;
				f[i][j] %= mod;
			}
		}
		a = f[n-1][m], b = f[n][m-1];
		memset(f, 0, sizeof(f));
		f[2][1] = (s[2][1] != '#');
		for(int i = 2; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				if(s[i][j] == '#') continue;
				f[i][j] += (f[i-1][j] + f[i][j-1]) % mod;
				f[i][j] %= mod;
			}
		}
		c = f[n-1][m], d = f[n][m-1];
		LL ret = ((a * d) % mod - (b * c) % mod + mod) % mod;
		printf("%lld\n", ret);
	}
	return 0;
}

哈，除草真开心啊！