HDU 4349 組合數奇數個數：Lucas 定理與二進制性質

問題描述

給定 n，求二項式係數 C(n,0), C(n,1), ..., C(n,n) 中奇數的個數。多組輸入，以 EOF 結束。

核心洞察：Lucas 定理模 2

Lucas 定理：對質數 p，將 n, m 寫成 p 進制 n = n_k...n_0, m = m_k...m_0，則

C(n,m) ≡ Π C(n_i, m_i) (mod p)

取 p=2，二進制位上 C(0,1)=0（偶數），C(1,0)=C(1,1)=1（奇數）。因此 C(n,m) 為奇數 ⟺ m 的二進制表示中每一位 ≤ n 對應位（即 m & n == m，或說 m 是 n 的子集）。

若 n 二進制中有 k 個 1，則滿足條件的 m 有 2^k 個（每個 1 位可選 0 或 1）。

算法

1. 計算 n 二進制中 1 的個數 k（__builtin_popcount 或循環）。
2. 答案為 2^k（1 << k）。

參考代碼 (C++)

#include 
int main() {
    long long n;
    while (scanf("%lld", &n) == 1) {
        int k = __builtin_popcountll(n);
        printf("%lld\n", 1LL << k);
    }
    return 0;
}

複雜度

時間 O(log n) 每測試案例，空間 O(1)。極其高效。

擴展思考

• 同理可求模任意質數 p 下非零係數個數：將 n 寫成 p 進制，各位數字為 d_i，答案為 Π (d_i + 1)。
• 打表找規律也是解決此類問題的有效手段。

總結

• Lucas 定理將大數組合數模質數轉化為逐位小數組合數乘積。
• 模 2 時，C(n,m) 奇數 ⟺ m 二進制位是 n 的子集。
• 答案直接等於 2^{popcount(n)}。