HDU 5698 瞬間移動：組合數學解法詳解（2016 百度之星）

問題背景

在一個無限大的矩形網格中，你初始位於左上角（第 1 行第 1 列）。每一步你可以選擇任意一個位於當前位置右下方的格子（即行號和列號都嚴格大於當前位置）並瞬間移動過去。請問到達第 n 行第 m 列的格子共有多少種不同的移動方案？答案需對 1,000,000,007 取模。

問題分析

觀察移動規則：每一步必須向右下移動，因此路徑是一條嚴格單調遞增的序列。從 (1,1) 到 (n,m) 至少需要 1 步，最多需要 (n-1)+(m-1) 步？實際上，因為可以跳躍任意距離，每一步只需保證目標格子在右下方即可。這等價於在 (n-1) 個向下移動和 (m-1) 個向右移動中，選擇若干步合併為一次「瞬間移動」。

更直觀的組合模型：將整個路徑看作從 (1,1) 到 (n,m) 的單調路徑，每一步必須增加行號和列號。這等價於在 (n+m-2) 個總步驟中選擇 (n-1) 個向下步驟（或 (m-1) 個向右步驟），但因為允許跳躍，實際上每一步至少增加 1 行和 1 列。因此有效步數為 (n-1) + (m-1) - (步數-1)？經過推導，方案數等於組合數 C(n+m-4, n-2)（或 C(n+m-4, m-2)）。

樣例驗證：n=4, m=5 → n+m-4=5, n-2=2 → C(5,2)=10，與樣例輸出一致。

解法實現

核心任務是計算大數組合數模 1e9+7。利用費馬小定理求模逆元，預計算階乘與逆元階乘，或直接線性計算：

// 計算 C(n, k) mod MOD
long long comb(long long n, long long k) {
    if (k < 0 || k > n) return 0;
    long long res = 1;
    for (long long i = 1, j = n; i <= k; ++i, --j) {
        res = res * j % MOD;
        res = res * mod_pow(i, MOD-2) % MOD; // 模逆元
    }
    return res;
}

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;

long long mod_pow(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

long long comb(long long n, long long k) {
    if (k < 0 || k > n) return 0;
    long long res = 1;
    for (long long i = 1, j = n; i <= k; ++i, --j) {
        res = res * j % MOD;
        res = res * mod_pow(i, MOD-2) % MOD;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, m;
    while (cin >> n >> m) {
        cout << comb(n + m - 4, n - 2) << '\n';
    }
    return 0;
}