【概述】

組合數取模，即計算組合數 ，由于?，同余定理對除法不適用，因此需要使用別的方法來解決這個問題

常見的方法有：使用逆元對組合數取模、遞推打表取模、盧卡斯定理、擴展盧卡斯定理等，這些方法應用的場景各不相同。

• 使用逆元：要求 p 是質數，時間復雜度 O(n)
• 遞推打表：要求 n、m 不大于 10000，時間復雜度 O(n^2)
• 盧卡斯定理：要求 p 是質數，且 m、n 很大但 p 很小 或者 n、m 不大但大于 p
• 擴展盧卡斯定理：要求?p 不是質數，且 m、n 很大但 p 很小 或者 n、m 不大但大于 p

【方法】

• 逆元、遞推打表：點擊這里
• 盧卡斯定理、擴展盧卡斯定理：點擊這里

【例題】

• Xiao Ming's Hope（HDU-4349）(公式推導)：點擊這里
• 機器人走方格（51Nod-1119）(盧卡斯定理)：點擊這里
• Combinations（LightOJ-1067）(盧卡斯定理)：點擊這里
• Problem Makes Problem（LightOJ-1102）(盧卡斯定理)：點擊這里
• Applese 的大獎（2019牛客寒假算法基礎集訓營 Day4-I）(逆元求組合數)：點擊這里
• いろはちゃんとマス目 / Iroha and a Grid（AtCoder-1974）(逆元求組合數)：點擊這里
• 11（AtCoder-2649）(容斥原理+遞推求逆元)：點擊這里

總結

以上是生活随笔為你收集整理的组合数学 —— 组合数取模的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。