超詳細手寫Lucas定理證明過程

• 寫此博文緣由
• 手寫證明過程

寫此博文緣由

為什麼寫這篇博文，主要是因為今天群組合數取模杠上了，acwing上求組合數的題目在将資料規模更新的情況下，解決的辦法也就有了變化。算法也真是奇妙的東西，人類也是非常聰明的物種，我為此常常自慚形穢，雖然如此，但仍停止不了我樂于學習的腳步。

1. 第一篇用組合數的性質，借用二維數組給推出來的。
2. 第二篇根據組合數的公式，用逆元的知識給算出來的。

3. 第三篇a,b的資料量達到了10^18，頓時傻眼，隻得翻書看看有沒有可以對此資料量友好的解的公式。結果發現Lucas定理可以讓它的計算時間大大提高。

   好的，那麼問題來了，Lucas定理我隻是在2017年聽zouyi帥哥說過，久仰大名而已，一直沒有沉下心去研究過。

手寫證明過程

于是今日花了些時間翻閱多篇部落格，并結合yxc大佬的講解視訊，終于弄懂了Lucas的證明過程。現将證明過程手稿貼于下方（部落格上書寫公式實在覺得難受），如有不正确的地方還請閱讀者批評指正。