BZOJ 1856：SCOI2010 字符串——卡特蘭數組合計數

題目描述

n 個 1 和 m 個 0 排列，任意前綴 1 的個數 ≥ 0 的個數。求方案數模 20100403。

卡特蘭數推廣

經典卡特蘭數 C(n,n) = C(2n,n)/(n+1)。推廣到 n 個 1、m 個 0（n ≥ m）：

Ans = C(n+m, n) - C(n+m, n+1)
    = (n-m+1)/(n+1) * C(n+m, n)

模算術實現

模數 P = 20100403 為質數。用費馬小定理求逆元：x⁻¹ ≡ x^{P-2} (mod P)。

C++ 實現

const int MOD = 20100403;
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 fact[4000005];
long long C(int n, int m) {
    if (m<0 || m>n) return 0;
    return fact[n] * mod_pow(fact[m], MOD-2) % MOD * mod_pow(fact[n-m], MOD-2) % MOD;
}
int main() {
    int n,m; scanf("%d%d",&n,&m);
    fact[0]=1;
    for(int i=1;i<=n+m;++i) fact[i]=fact[i-1]*i%MOD;
    long long ans = (C(n+m,n) - C(n+m,n+1) + MOD) % MOD;
    printf("%lld\n", ans);
    return 0;
}

複雜度

• 預計算階乘：O(n+m)
• 單次查詢：O(log MOD)