Lattice Path Counting

IKhông điểm cố định

Số hoán vị không có $i$ nào ở đúng vị trí $i$: gọi $A_i$ là tập hoán vị giữ nguyên $i$; một giao $k$ tập có $(n - k)!$ phần tử, nên

Cũng có truy hồi gọn: quà của người 1 tới người $j \ne 1$ ($n - 1$ cách). Nếu $j$ đưa lại quà cho 1 thì còn $D_{n-2}$ cách cho những người khác. Nếu không thì coi “không nhận quà của 1” như “không nhận quà của mình” cho $j$, còn $D_{n-1}$ cách. Vậy $D_n = (n - 1)(D_{n-1} + D_{n-2})$, $D_1 = 0$, $D_2 = 1$.

Hình dưới liệt kê mọi hoán vị không điểm cố định, chia theo việc người nhận quà của 1 có trả lại cho 1 hay không. Kéo $n$ để xem.

Ví dụHoán vị không điểm cố định

Đề. $n \le 10^6$ em, mỗi em một món quà. Đếm cách phát sao cho không em nào nhận lại quà của mình, theo mô-đun $10^9 + 7$.

Lời giải. Truy hồi $D_n = (n - 1)(D_{n-1} + D_{n-2})$ với $D_0 = 1$, $D_1 = 0$, đúng như lập luận ở trên. Chỉ cần hai giá trị trước, nên giữ hai biến thay cho cả mảng.

a, b lần lượt là $D_{i-2}$, $D_{i-1}$. Mỗi vòng tính $D_i$ rồi dời hai biến. $(i - 1)$ tới $10^6$ nhân một số dưới $10^9 + 7$ vẫn vừa long long.

ll a = 1, b = 0;
for (ll i = 2; i <= n; i++) {
    ll c = (i - 1) * ((a + b) % MOD) % MOD;
    a = b, b = c;
}

Với $n = 1$ vòng không chạy và in $D_1 = 0$: một em thì không cách nào để em đó nhận quà người khác.

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

const ll MOD = 1e9 + 7;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n;
    cin >> n;
    ll a = 1, b = 0;
    for (ll i = 2; i <= n; i++) {
        ll c = (i - 1) * ((a + b) % MOD) % MOD;
        a = b, b = c;
    }
    cout << b << '\n';
}

ChạyInput1

Output0

Độ phức tạp: $O(n)$.

IINguyên lý phản xạ

Đường đi trên lưới gồm $a$ bước lên, $b$ bước xuống, bắt đầu ở độ cao $h \ge 0$. Đếm những đường không xuống dưới 0: lấy tổng $\binom{a + b}{a}$ trừ các đường chạm $-1$. Lật phần đường trước lần chạm $-1$ đầu tiên qua đường $y = -1$ cho một song ánh với các đường bất kỳ từ $-h - 2$ tới cùng điểm cuối; số đường đó là $\binom{a + b}{a + h + 1}$. Vậy

Với $h = 0$, $a = b = n/2$, đây là số Catalan $\frac{1}{n/2 + 1}\binom{n}{n/2}$: số dãy ngoặc đúng dài $n$.

Trong hình, đường xanh có chạm $-1$ thì phần trước lần chạm đầu được lật (cam): mỗi đường xấu ứng đúng một đường xuất phát từ $-h - 2$.

Ví dụHoàn thiện tiền tố ngoặc

Đề. Độ dài $n \le 10^6$ và một tiền tố ngoặc dài $k$. Đếm số cách nối thêm để được dãy ngoặc đúng dài $n$, theo mô-đun $10^9 + 7$.

Lời giải. Coi ngoặc mở là bước lên, ngoặc đóng là bước xuống. Dãy ngoặc đúng là đường đi không xuống dưới 0 và kết thúc ở 0. Tiền tố cho trước đưa ta tới độ cao $h$, đã dùng op ngoặc mở và cl ngoặc đóng. Phần nối thêm cần đúng $a = n/2 - op$ bước lên và $b = n/2 - cl$ bước xuống, xuất phát từ độ cao $h$ và không xuống dưới 0. Công thức phản xạ cho $\binom{a + b}{a} - \binom{a + b}{a + h + 1}$.

Bước 1: đọc tiền tố. Theo dõi độ cao h; xuống dưới 0 ở bất kỳ lúc nào thì in 0 ngay.

for (char c : s) {
    if (c == '(') h++, op++;
    else h--;
    if (h < 0) {
        cout << 0 << '\n';
        return 0;
    }
}

Bước 2: các trường hợp vô nghiệm. $n$ lẻ, hay tiền tố dùng quá $n/2$ ngoặc một loại.

if (n % 2 || op > n / 2 || cl > n / 2) {
    cout << 0 << '\n';
    return 0;
}

Bước 3: công thức phản xạ. C(n, k) trả 0 khi $k$ ngoài $[0, n]$, nên khi $a + h + 1 > a + b$ (không đường nào chạm $-1$ được) số hạng thứ hai tự bằng 0. Phép trừ cộng thêm MOD.

ll a = n / 2 - op, b = n / 2 - cl;
cout << (C(a + b, a) - C(a + b, a + h + 1) + MOD) % MOD << '\n';

Kiểm với mẫu: $n = 2$, tiền tố (, có $h = 1$, $a = 0$, $b = 1$; $\binom{1}{0} - \binom{1}{2} = 1$.

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

const ll MOD = 1e9 + 7;
const int N = 1e6 + 5;
ll fac[N], ifac[N];

ll power(ll a, ll b) {
    ll r = 1;
    a %= MOD;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

ll C(ll n, ll k) {
    if (k < 0 || k > n) return 0;
    return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n;
    string s;
    cin >> n >> s;
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[n] = power(fac[n], MOD - 2);
    for (int i = n; i >= 1; i--) ifac[i - 1] = ifac[i] * i % MOD;
    ll h = 0, op = 0;
    for (char c : s) {
        if (c == '(') h++, op++;
        else h--;
        if (h < 0) {
            cout << 0 << '\n';
            return 0;
        }
    }
    ll cl = s.size() - op;
    if (n % 2 || op > n / 2 || cl > n / 2) {
        cout << 0 << '\n';
        return 0;
    }
    ll a = n / 2 - op, b = n / 2 - cl;
    cout << (C(a + b, a) - C(a + b, a + h + 1) + MOD) % MOD << '\n';
}

ChạyInput2
(

Output1

Độ phức tạp: $O(n)$.

IIIÔ cấm đầu tiên

Đường đi đơn điệu (chỉ xuống, sang phải) từ $(1,1)$ tới $(r, c)$ có $\binom{r + c - 2}{r - 1}$ cách. Có $n$ ô cấm thì bao hàm loại trừ trên mọi tập ô là $2^n$, nhưng chỉ cần phân loại theo ô cấm đầu tiên mà đường chạm: sắp các ô cấm theo $(r, c)$, thêm đích làm ô cuối, gọi $dp_i$ là số đường từ gốc tới ô $i$ không qua ô cấm nào trước đó:

Mỗi đường xấu tới $i$ có đúng một ô cấm đầu tiên $j$, nên không bị trừ hai lần. Tổng $O(n^2)$.

Ví dụĐường đi tránh ô cấm

Đề. Lưới $h \times w$ ($\le 10^5$), $n \le 2000$ ô đen. Đếm đường đi xuống, sang phải từ $(1,1)$ tới $(h, w)$ không qua ô đen, theo mô-đun $10^9 + 7$.

Lời giải. Sắp các ô đen theo $(r, c)$ và thêm đích $(h, w)$ làm ô cuối. $dp_i$ là số đường từ $(1, 1)$ tới ô $i$ không đi qua ô đen nào trước khi tới $i$. Lấy mọi đường tới $i$ rồi trừ các đường xấu, phân loại theo ô đen đầu tiên $j$ mà đường chạm: có $dp_j$ cách tới $j$ sạch, rồi $\binom{\Delta r + \Delta c}{\Delta r}$ cách đi tiếp tới $i$. Mỗi đường xấu có đúng một ô đen đầu tiên nên bị trừ đúng một lần.

Bước 1: sắp. Ô có thể đi trước ô $i$ (cả hai tọa độ không lớn hơn) luôn đứng trước $i$, nên khi tính dp[i] mọi dp[j] cần dùng đã xong. Bảng giai thừa dựng tới $2 \cdot 10^5$, đủ cho $\binom{h + w - 2}{h - 1}$.

sort(p, p + n);
p[n] = {h, w};

Bước 2: trừ đường xấu. Chỉ trừ những ô $j$ nằm ở góc trên trái của $i$; ô khác không thể nằm trên đường đơn điệu tới $i$.

dp[i] = C(r + c - 2, r - 1);
for (int j = 0; j < i; j++)
    if (p[j].first <= r && p[j].second <= c) {
        int dr = r - p[j].first, dc = c - p[j].second;
        dp[i] = (dp[i] - dp[j] * C(dr + dc, dr) % MOD + MOD) % MOD;
    }

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

const ll MOD = 1e9 + 7;
const int N = 2e5 + 5;
ll fac[N], ifac[N], dp[2005];
pair<int, int> p[2005];

ll power(ll a, ll b) {
    ll r = 1;
    a %= MOD;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

ll C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int h, w, n;
    cin >> h >> w >> n;
    fac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[N - 1] = power(fac[N - 1], MOD - 2);
    for (int i = N - 1; i >= 1; i--) ifac[i - 1] = ifac[i] * i % MOD;
    for (int i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
    sort(p, p + n);
    p[n] = {h, w};
    for (int i = 0; i <= n; i++) {
        int r = p[i].first, c = p[i].second;
        dp[i] = C(r + c - 2, r - 1);
        for (int j = 0; j < i; j++)
            if (p[j].first <= r && p[j].second <= c) {
                int dr = r - p[j].first, dc = c - p[j].second;
                dp[i] = (dp[i] - dp[j] * C(dr + dc, dr) % MOD + MOD) % MOD;
            }
    }
    cout << dp[n] << '\n';
}

ChạyInput2 2 1
1 2

Output1

Độ phức tạp: $O(n^2) = 4 \cdot 10^6$ phép.

IVBổ đề Burnside

Khi hai cấu hình được coi là một nếu một phép biến đổi trong nhóm $G$ (như các phép quay) đưa cái này thành cái kia, số lớp tương đương là trung bình số cấu hình bất động qua các phép biến đổi:

Vòng cổ $n$ hạt, $m$ màu, nhóm gồm $n$ phép quay: phép quay $k$ bước chia các hạt thành $\gcd(k, n)$ chu trình, mỗi chu trình phải cùng màu, nên cố định $m^{\gcd(k, n)}$ cách tô. Đáp án $\frac{1}{n} \sum_{k=0}^{n-1} m^{\gcd(k, n)}$; gom theo ước $d$ của $n$ được $\frac{1}{n} \sum_{d \mid n} \varphi(n/d)\, m^d$.

Trong hình, các hạt cùng màu là cùng chu trình của phép quay $k$ bước; bên phải là số cách tô bất động cho từng $k$.

Ví dụVòng màu dưới phép quay

Đề. Vòng cổ $n \le 10^6$ hạt, $m \le 10^6$ màu; hai vòng như nhau nếu quay được thành nhau. Đếm số vòng theo mô-đun $10^9 + 7$.

Lời giải. Bổ đề Burnside với nhóm $n$ phép quay: phép quay $k$ bước có $\gcd(k, n)$ chu trình hạt, mỗi chu trình một màu, nên giữ nguyên $m^{\gcd(k, n)}$ cách tô. Số vòng khác nhau là trung bình các số đó, $\frac{1}{n} \sum_{k=0}^{n-1} m^{\gcd(k, n)}$. Chia cho $n$ là nhân nghịch đảo của $n$ (theo Fermat, $n < p$ nên có nghịch đảo).

pw[i] $= m^i$ tính sẵn tới $n$. $k = 0$ là phép quay không làm gì, __gcd(0, n) = n, giữ nguyên cả $m^n$ cách tô.

for (ll k = 0; k < n; k++) sum = (sum + pw[__gcd(k, n)]) % MOD;
cout << sum * power(n, MOD - 2) % MOD << '\n';

Gom theo ước như công thức với $\varphi$ ở trên thì nhanh hơn, nhưng ở đây chưa cần.

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

const ll MOD = 1e9 + 7;

ll power(ll a, ll b) {
    ll r = 1;
    a %= MOD;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n, m;
    cin >> n >> m;
    vector<ll> pw(n + 1);
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * m % MOD;
    ll sum = 0;
    for (ll k = 0; k < n; k++) sum = (sum + pw[__gcd(k, n)]) % MOD;
    cout << sum * power(n, MOD - 2) % MOD << '\n';
}

ChạyInput1 1

Output1

Độ phức tạp: $O(n \log n)$.