LGV 引理

https://en.wikipedia.org/wiki/Lindström–Gessel–Viennot_lemma

简单的例子

两个人从 (0, 0)走到 (n, m) 要求除了起点和终点不能相遇

转化：
从(1,0)走到(n,m-1)，方案数是 C(n+m-2，n-1)
从(0,1)走到(n-1,m)，方案数是 C(n+m-2，n-1)
但其中有一些方案，两个人的路线相交了，计算相交的方案数
从(1,0)走到(n-1,m)，方案数是 C(n+m-2，m)
从(0,1)走到(n,m-1)，方案数是 C(n+m-2，n)
最终答案是
C(n+m-2，n-1) * C(n+m-2，m-1) - C(n+m-2，m) * C(n+m-2，n)

参考题目

CF348D Turtles

https://codeforces.com/problemset/problem/348/D
https://www.luogu.com.cn/problem/CF348D

参考代码

#include <bits/stdc++.h>
using namespace std;
const int p = 1000000007;
int n, m;
char s[3020];
int f[3020][3020]; // from (1, 2) to every other point
int g[3020][3020]; // from (2, 1) to every other point
int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m;
	f[0][2] = 1;
	g[2][0] = 1;
	for (int i = 1; i <= n; i++)
	{
		cin >> s;
		for (int j = 1; j <= m; j++)
		{
			if (s[j - 1] == '.')
			{
				f[i][j] = (f[i - 1][j] + f[i][j - 1]) % p;
				g[i][j] = (g[i - 1][j] + g[i][j - 1]) % p;
			}
		}
	}
	cout << ((long long)f[n - 1][m] * g[n][m - 1] % p + p - (long long)g[n - 1][m] * f[n][m - 1] % p) % p << endl;
	return 0;
}

题解

P6657 【模板】LGV 引理

https://www.luogu.com.cn/problem/P6657

题目描述

这是一道模板题。

有一个 $n\times n$ 的棋盘，左下角为 $(1,1)$，右上角为 $(n,n)$，若一个棋子在点 $(x,y)$，那么走一步只能走到 $(x+1,y)$ 或 $(x,y+1)$。

现在有 $m$ 个棋子，第 $i$ 个棋子一开始放在 $(a_i,1)$，最终要走到 $(b_i,n)$。问有多少种方案，使得每个棋子都能从起点走到终点，且对于所有棋子，走过路径上的点互不相交。输出方案数 $\bmod\ 998244353$ 的值。

两种方案不同当且仅当存在至少一个棋子所经过的点不同。

输入格式

本题有多组数据

第一行一个整数 $T$，表示该测试点的数据组数。

对于每组数据：

第一行两个整数 $n,m$，分别表示棋盘的大小和起点终点的数量。

接下来 $m$ 行，每行 $2$ 个整数 $a_i,b_i$，其意义已在题目描述中说明。

输出格式

对于每一组数据，输出一行一个整数表示方案数 $\bmod\ 998244353$ 的值。

样例 #1

样例输入 #1

3
3 2
1 2
2 3
5 2
1 3
3 5
10 5
3 5
4 7
5 8
7 9
9 10

样例输出 #1

3
155
2047320

提示

• 对于 $30\%$ 的数据，$n\leq 100$，$m\leq 8$。

• 对于 $100\%$ 的数据，$T\leq5$，$2\leq n\leq10^6$，$1\leq m\leq100$，$1\leq a_1\leq a_2\leq \dots\leq a_m\leq n$，$1\leq b_1\leq b_2\leq \dots\leq b_m\leq n$。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int t, n, m;
int a[100][100];
int x[100];
int y[100];
int f[2000020];
int v[2000020];
int C(int n, int m)
{
	return n < m ? 0 : (long long)f[n] * v[m] % mod * v[n - m] % mod;
}
int main()
{
	v[0] = v[1] = f[0] = 1;
	for (int i = 2; i < 2000010; i++)
	{
		v[i] = (long long)(mod - mod / i) * v[mod % i] % mod;
	}
	for (int i = 1; i < 2000010; i++)
	{
		f[i] = (long long)f[i - 1] * i % mod;
		v[i] = (long long)v[i - 1] * v[i] % mod;
	}
	scanf("%d", &t);
	for (int tt = 0; tt < t; tt++)
	{
		scanf("%d%d", &m, &n);
		for (int i = 0; i < n; i++)
		{
			scanf("%d%d", &x[i], &y[i]);
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				a[i][j] = C(m - 1 + y[j] - x[i], m - 1);
			}
		}
		int ans = 1;
		for (int i = 0; i < n; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				while (a[j][i])
				{
					int t = a[i][i] / a[j][i];
					for (int k = 0; k < n; k++)
					{
						a[i][k] = (a[i][k] - (long long)a[j][k] * t) % mod;
					}
					swap(a[i], a[j]);
					ans = -ans;
				}
			}
			ans = (long long)ans * a[i][i] % mod;
		}
		if (ans < 0)
		{
			ans += mod;
		}
		printf("%d\n", ans);
	}
	return 0;
}

题解