DDOSvoid's Blog

Luogu P6657 【模板】LGV 引理

发表于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

题目描述

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

简要题意：有一个 $n\times n$ 的棋盘，左下角为 $(1,1)$，右上角为 $(n,n)$，棋子只能向右或者向上走，现在有 $m$ 个棋子，第 $i$ 个棋子一开始放在 $(a_i,1)$，要走到 $(b_i,n)$，问有多少种方案，使得每个棋子都能从起点走到终点，且对于所有棋子，走过的路径互不相交，方案数对 $998244353$ 取模

$n\le 10^6,m\le 100$

Solution

考虑 $LGV$​ 引理构造矩阵 $A_{i,j}=\binom{b_j-a_i+n-1}{n-1}$​，因为只有当 $a_i$​ 对应的 $b_{\sigma(i)}$​ 为 $b_i$​ 时才可能有解，容易得到方案数即为 $det(A)$​​，高斯消元求解行列式即可

时间复杂度 $O(n+m^3)$

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
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#define maxn 110
#define maxm 2000010
#define ll long long
using namespace std;

const int p = 998244353;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s; 
}

int n, m, a[maxn], b[maxn];

ll fac[maxm], inv[maxm];
void init_C(int n) {
    fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
    inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p; 
}

ll C(int n, int m) { return n < m ? 0 : fac[n] * inv[m] % p * inv[n - m] % p; } 

ll g[maxn][maxn];
int Gauss(int n) {
    ll res = 1; 
    for (int i = 1; i <= n; ++i) {
        int pos = -1;
        for (int j = i; j <= n; ++j) if (g[j][i]) pos = j;
        if (pos == -1) return 0; swap(g[i], g[pos]); res *= pos == i ? 1 : -1;
        res = res * g[i][i] % p; ll inv = pow_mod(g[i][i], p - 2);
        for (int j = i + 1; j <= n; ++j) 
            for (int k = n; k >= i; --k)
                g[j][k] = (g[j][k] - g[j][i] * inv % p * g[i][k]) % p;
    } return res;
}

void work() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> a[i] >> b[i];
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= m; ++j) g[i][j] = C(b[j] - a[i] + n - 1, n - 1);
    cout << (Gauss(m) + p) % p << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T; init_C(2000000);
    while (T--) work();
    return 0;
}