HDU 4828 Grids：卡特蘭數與擴展歐幾里得算法

問題轉化

將上一行視為入棧、下一行視為出棧，合法方案數即為卡特蘭數。遞推公式：

C(n) = C(n-1) * (4n-2) / (n+1)

模數 MOD = 1e9+7 為質數，除法轉為乘以模逆元，利用擴展歐幾里得算法求解。

核心代碼

#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 1000005;
const ll MOD = 1e9+7;
ll dp[N];

ll extendGcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll d = extendGcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

ll solve(ll n) { // 求 n 的模逆元
    ll x, y;
    extendGcd(n, MOD, x, y);
    x = (x % MOD + MOD) % MOD;
    return x;
}

void init() {
    dp[1] = 1; dp[2] = 2;
    for (ll i = 3; i < N; i++)
        dp[i] = (dp[i-1] * (4 * i - 2) % MOD * solve(i + 1)) % MOD;
}

int main() {
    int cas, n; scanf("%d", &cas);
    init();
    for (int i = 1; i <= cas; i++) {
        scanf("%d", &n);
        printf("Case #%d:\n%lld\n", i, dp[n]);
    }
    return 0;
}

關鍵點

• 預計算 dp 陣列，查詢 O(1)。
• 模逆元計算確保除法在模意義下正確。
• 卡特蘭數遞推避免大數組合數直接計算。