HDU 3304 Interesting Yang Hui Triangle：Lucas 定理求模質數非零二項式係數

題目大意

給定質數 P (<1000) 和行號 N (≤10^9)，求楊輝三角第 N 行中模 P 不為 0 的元素個數。即統計 C(N, k) mod P ≠ 0 的 k 個數（0 ≤ k ≤ N）。

Lucas 定理

將 N、k 寫成 P 進制：
N = a_m P^m + ... + a_1 P + a_0
k = b_m P^m + ... + b_1 P + b_0
則 C(N,k) ≡ ∏ C(a_i, b_i) (mod P)。
乘積模 P 不為 0 ⇔ 每個因子 C(a_i, b_i) mod P ≠ 0 ⇔ 對所有 i，0 ≤ b_i ≤ a_i（因 P 為質數，C(a,b) 只有當 b>a 時才為 0）。

計數公式

對每一位 a_i，合法的 b_i 有 a_i + 1 種選擇（0~a_i）。各位獨立，總方案數為 ∏ (a_i + 1)。

算法流程

1. 將 N 分解為 P 進制位數組 digits[]。
2. 答案初始為 1，遍歷每位 d，ans = ans * (d + 1) % MOD（題目要求模 10007？原題輸出方案數，通常不模，但代碼中用了 MOD=10000，需確認題目具體要求）。
3. 輸出 ans。

複雜度

分解 P 進制 O(log_P N) ≤ 30 步，極快。

參考代碼（C++）