HDU 5187 計數問題：排列中單調段的組合數學解法

問題描述

從 1~n 的排列中，有多少種排列滿足：存在某個位置 i，使得前綴 a₁~a_i 單調遞增或遞減，且後綴 a_i~a_n 也單調遞增或遞減。答案模 p 輸出。

組合數學推導

觀察條件：選定分割點 i 後，前 i 個數從 n 個中選出，其排列若單調則只有 1 種（升序或降序）；同理後 n-i 個數也只有 1 種排列。因此，對於固定 i，方案數 = C(n, i) × 2 × 2 = 4·C(n, i)？

實際更簡單：無論 i 取何值，只要確定哪些數在前綴，其排列方式完全固定（單調）。所以本質上是將 n 個數分為兩組，每組內部按單一順序排列。每個數有「屬於前綴」或「屬於後綴」兩種選擇，共 2ⁿ 種分法。但需排除全在前綴（後綴空）和全在後綴（前綴空）的情況，因為題目隱含 i 在中間？原題分析給出：

答案 = 2ⁿ - 2

（n=1 時特判為 1）。

模冪計算與防溢出

n 較大（≤10⁹），需快速冪計算 2ⁿ mod p。但 p 不一定是質數，且乘法可能溢出 64 位，需用快速乘（類似快速冪，用加法代替乘法）：

long long mul_mod(long long a, long long b, long long mod) {
    long long res = 0;
    while (b) {
        if (b & 1) res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}

long long pow_mod(long long a, long long b, long long mod) {
    long long res = 1;
    while (b) {
        if (b & 1) res = mul_mod(res, a, mod);
        a = mul_mod(a, a, mod);
        b >>= 1;
    }
    return res;
}

完整邏輯

while (scanf("%lld%lld", &n, &p) != EOF) {
    if (n == 1) { printf("%lld\n", 1 % p); continue; }
    long long ans = pow_mod(2, n, p);
    ans = (ans - 2 + p) % p;
    printf("%lld\n", ans);
}

總結

HDU 5187 看似排列計數，實則是組合恆等式 Σ C(n,i) = 2ⁿ 的直接應用。關鍵在於識別「單調排列方式唯一」將問題轉化為子集選擇，並處理大數模運算中的乘法溢出（快速乘）。