10.21 路径组计数

题意

给定一个 (N imes M) 的矩阵，定义一次移动为向右移动一个单位或向上移动一个单位

你要从 ((1,1)) 移动至 ((N,M))， 且要走两次，我们称这两次的路线分别为 (A,B)

我们称一个 ((A,B)) 二元组是合法的，则 (A,B) 除了在 ((1,1),(N,M)) 以外，其它经过的格子都不相同

请你统计所有合法二元组的数量。注意 ((A,B)) 与 ((B,A)) 为相同的二元组

解法

首先有一个 naive 的想法：既然路线只能在 ((1,1),(N,M)) 重复，那么两条路线的起点和终点一定分别是((1,2),(2,1)) 与 ((N-1,M),(N,M-1))

设 (calc(N,M)) 为 ((1,1)) 到 ((N,M)) 的路径条数，这个可以预处理组合数后 (O(1)) 计算出来

那么答案即为 (calc(N-1,M-1)^2)

很容易发现这样计算是错误的，因为这样还是会有路线重复的二元组

仔细观察就可以发现，任意一个按照上面方式计算的不合法的二元组（即两条路线在某处有交集）

它们一定唯一对应一组起点和终点分别为 ((1,2),(2,1)) 与 ((N,M-1),(N-1,M)) 的路径

因此答案最后为 (calc(N-1,M-1)^2 - calc(N-2,M) - calc(N,M-2))

代码

#include <cstdio>

using namespace std;

const int MAX_N = 2e6 + 10;
const int mod = 998244353;

int T, N, M;

int fac[MAX_N], Ifac[MAX_N];

inline void inc(int& x, int y) { (x += y) >= mod ? x -= mod : 0; }
inline int mul(int x, int y) { return 1LL * x * y % mod; }
inline int sqr(int x) { return 1LL * x * x % mod; }

int fsp(int x, int y = mod - 2) {
	int res = 1;
	for (; y; x = sqr(x), y >>= 1)  if (y & 1)  res = mul(res, x);
	return res;
}

void init() {
	int lim = 2e6;
	fac[0] = 1;
	for (int i = 1; i <= lim; ++i)  fac[i] = mul(fac[i - 1], i);
	Ifac[lim] = fsp(fac[lim]);
	for (int i = lim - 1; i >= 0; --i)  Ifac[i] = mul(Ifac[i + 1], i + 1);
}

int C(int n, int m) { return mul(fac[n], mul(Ifac[m], Ifac[n - m])); }

int calc(int n, int m) { return C(n + m - 2, n - 1); }

int main() {
	
	init();
	
	scanf("%d", &T);
	
	while (T--) {
		scanf("%d%d", &N, &M);
		printf("%d
", (mod + sqr(calc(N - 1, M - 1)) - mul(calc(N, M - 2), calc(N - 2, M))) % mod);
	}
		
	return 0;
}