Lindström–Gessel–Viennot lemma

概要

格子点上で、n 組の始点と終点 $(a_1, a_2, \ldots, a_n), (b_1, b_2, \ldots, b_n)$ が定まっているとして、それらが交差しないようなパスの選び方をカウントできる定理である。($a_i$ をどの $b_j$ と対応付けるか、まで含めて。)
後にこの定理を用いて解ける問題を挙げる。

主張

$G$ を局所的に有限なDAGとする。
始点集合を $A = \{a_1, \ldots, a_n\}$ とし、終点集合を $B = \{b_1, \ldots, b_n\}$ とする。
辺には重みがついており、パス $P$ に対して $w(P)$ で $P$ 上の辺の重みの積と定義する。
また、$e(a, b) := \sum_{P : a \rightarrow b}w(P)$ と定義する。
もしすべての辺の重みが 1 であるならば、$e(a, b)$ は $a$ から $b$ へ行く方法の総数に対応する。

ここで、
$M = \left(
\begin{array}{cccc}
e(a_1, b_1) & e(a_1, b_2) & \cdots & e(a_1, b_n) \\
e(a_2, b_1) & e(a_2, b_2) & \cdots & e(a_2, b_n) \\
\vdots & \vdots & & \vdots \\
e(a_n, b_1) & e(a_n, b_2) & \cdots & e(a_n, b_n)
\end{array}
\right)$
とおく。
$n$ 組の $A$ から $B$ へのパス $P = (P_1, P_2, \ldots, P_n)$ が交差しないとは、以下の性質を満たすことである。

  • $\{1, \ldots, n\}$ のある順列 $\pi$ があって、パス $P_i$ は $a_i$ から $b_{\pi(i)}$ へのパスと表される
  • $i \neq j$ ならば、$P_i$ と $P_j$ は端点も含め共通な頂点を持たない

すると、$det(M)$ は $A$ から $B$ への $n$ 組非交差パス $P = (P_1, \ldots, P_n)$ についての符号付き総和となる。
つまり、 $\det (M) = \sum_{(P_1, \ldots, P_n) : A \rightarrow B} sgn(\pi(P)) \prod_{i=1}^{n}w(P_i)$ である。

とくに、2つの性質を満たす順列 $\pi$ が identity な順列、つまりすべての $i$ について $\pi(i) = i$ となる順列しか無く、かつ辺の重みがすべて 1 の場合、$\det(M)$ は $A$ から $B$ への $n$ 組非交差パスのとり方の総数と等しくなる。

証明

そのうち(ごめんなさい)

問題概要

n * m のグリッドが与えられる。いくつかのマスは障害物があり通れない。
2人が座標 (0, 0) からスタートして (n - 1, m - 1) に到達する移動方法で、同じマスを通らないようなもの(ただし始点と終点はよい)は何通りあるか。
許される移動方法は、今の座標を (x, y) として (x + 1, y) か (x, y + 1) に移動することだけである。

・2 <= n, m <= 3000

解法

さっきの定理で解ける。
今回であれば、始点として $A = \{(0, 1), (1, 0)\}$ を、終点として $B = \{(n - 2, m - 1), (n - 1, m - 2)\}$ を与えて適用できる。
適用できる理由は、順列 $\pi$ としては identity なものしかありえないからである。
具体的には、$(0, 1)$ と $(n - 1, m - 2)$ を対応付ければ、かならずパスが交差してしまうということである。
よって、求める答えは、行列式
$\left|
\begin{array}{cc}
f(a_1, b_1) & f(a_1, b_2) \\
f(a_2, b_1) & f(a_2, b_2)
\end{array}
\right|$
である。ただし、$f(a_i, b_i)$ は $a_i$ から $b_i$ への移動方法の総数を表し、これは簡単な dp で O(nm) で解ける。

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr int mod = 1e9 + 7;

int add(int a, int b) {
    a += b;
    if(a >= mod) a -= mod;
    return a;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<string> v(n);
    for(int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    vector<vector<int>> dp(n, vector<int>(m));
    auto calc = [&] (int sy, int sx, int gy, int gx) {
        if(v[sy][sx] == '#') return 0;
        for(int i = 0; i < n; ++i) {
            fill(begin(dp[i]), end(dp[i]), 0);
        }
        dp[sy][sx] = 1;
        for(int i = sy; i < n; ++i) {
            for(int j = sx; j < m; ++j) {
                if(v[i][j] == '#' || (i == sy && j == sx)) continue;
                if(i != 0) dp[i][j] = add(dp[i][j], dp[i - 1][j]);
                if(j != 0) dp[i][j] = add(dp[i][j], dp[i][j - 1]);
            }
        }
        return dp[gy][gx];
    };

    int ans = (ll)calc(1, 0, n - 1, m - 2) * calc(0, 1, n - 2 , m - 1) % mod;
    (ans += mod - (ll)calc(1, 0, n - 2, m - 1) * calc(0, 1, n - 1, m - 2) % mod) %= mod;
    cout << ans << endl;
}

参考文献

Lindström–Gessel–Viennot lemma - Wikipedia
主張はほとんどここからのパクリです。