一个神奇的东西。今年NOI考了，算是填个坑吧。话说去年徐神在林荫集训的时候考场上自己把这东西推了出来（sto 徐神 orz）

仅仅适用于有向无环图。

令 \(\omega(P)\) 表示路径 \(P\) 上的边权积，\(e(u,v)\) 表示 \(u\) 到 \(v\) 的所有路径额的 \(\omega\) 值之和，即 \(\sum \omega(P:u\rightarrow v)\)。有两个大小为 \(n\) 的集合， 分别为起点集合 \(A\) 和 终点集合 \(B\), 令矩阵 \(M\) 为：

\[M=\left(\begin{matrix}e(A_1,B_1)&e(A_1,B_2)&...&e(A_1,B_n)\\. & &&.\\.&&&.\\.&&&.\\e(A_n,B_1)&e(A_n,B_2)&...&e(A_n,B_n)\end{matrix}\right) \]

再令 \(S:A\rightarrow B\) 为从 \(A\) 到 \(B\) 的一组不相交路径， \(\sigma(S)\) 表示一个排列，\(\S_i\) 表示从 \(A_i\) 到 \(B_{\sigma(S)_i}\) 的路径，且对于 \(i\neq j\), \(S_i,S_j\) 不相交。 让 \(\mu(\sigma)\) 表示 \(\sigma\) 中的逆序对个数，则：

\[\det M = \sum_{S:A\rightarrow B} (-1)^{\mu(\sigma(S))} \prod_{i=1}^n \omega(S_i) \]

证明？OI无证明 大概是写出行列式的的表达式然后推到，最后构造一个双射证上面那个式子里的 \(S\) 定义换成相交路径就变成 0， 反正没啥用我具体的也不会就不写了。

洛谷版题：

网格上路径单调，只有 \(\sigma = \{1,2,3,...,n\}\) 一种情况才能相交。我们设所有边权为 \(1\), \(e(a_i,b_j)\) 就是个组合数学问题，在 \(b_j-a_i+n-1\) 步里选 \(n-1\)步横着走。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 105, mod = 998244353;

int f[N][N], m, n;

inline int power(int a, int b) {
	int k = b, y = a, t = 1;
	while (k) {
		if (k & 1) t = (1ll * t * y) % mod;
		y = (1ll * y * y) % mod; k >>= 1; 
	} return t;
}

inline int det() {
	int ans = 1, sg = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			while (f[j][i]) {
				const int tmp = (1ll * f[i][i] * power(f[j][i], mod - 2)) % mod;
				for (int k = i; k <= n; ++k)
					f[i][k] = (1ll * f[i][k] - 1ll * tmp * f[j][k]) % mod + mod % mod;
				swap(f[i], f[j]); sg = -sg;
			}
		} if (!f[i][i]) return 0;
		ans = (1ll * ans * f[i][i]) % mod;
	} return (ans * sg + mod) % mod;
}

int fac[2000005], invfac[2000005], a[N], b[N];

inline int C(int n, int m) {
	if (n < m) return 0;
	return ((1ll * (1ll * fac[n] * invfac[m]) % mod) * invfac[n - m]) % mod;
}

int main() {
	fac[0] = 1;
	for (int i = 1; i <= 2000000; ++i) fac[i] = (1ll * i * fac[i - 1]) % mod;
	invfac[2000000] = power(fac[2000000], mod - 2);
	for (int i = 1999999; ~i; --i) invfac[i] = (1ll * (i + 1) * invfac[i + 1]) % mod;
	int T; scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &m, &n);
		for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i], &b[i]);
		memset(f, 0, sizeof f);
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				f[i][j] = C(m - 1 + b[j] - a[i], m - 1);
		printf("%d\n", det());
	} return 0;
}