數學問題 貪心 組合數 lucas定理
題目描述 Description
邪教喜歡在各種各樣空間内跳。
現在，邪教來到了一個二維平面。在這個平面内，如果邪教目前跳到了(x,y)，那麼他下一步可以選擇跳到以下4個點：(x-1,y), (x+1,y), (x,y-1), (x,y+1)。
而每當邪教到達一個點，他需要耗費一些體力，假設到達(x,y)需要耗費的體力用C(x,y)表示。
對于C(x,y)，有以下幾個性質：
1、若x=0或者y=0，則C(x,y)=1。
2、若x>0且y>0，則C(x,y)=C(x,y-1)+C(x-1,y)。
3、若x<0且y<0，則C(x,y)=無窮大。
現在，邪教想知道從(0,0)出發到(N,M)，最少花費多少體力（到達(0,0)點花費的體力也需要被算入）。
由于答案可能很大，隻需要輸出答案對10^9+7取模的結果。
輸入描述 Input Description
讀入兩個整數N，M，表示邪教想到達的點。
輸出描述 Output Description
輸出僅一個整數，表示邪教需要花費的最小體力對10^9+7取模的結果。
樣例輸入 Sample Input
1 2
樣例輸出 Sample Output
6
資料範圍及提示 Data Size & Hint
對于10%的資料，滿足N, M<=20；
對于30%的資料，滿足N, M<=100；
對于60%的資料，滿足min(N,M)<=100；
對于100%的資料，滿足0<=N, M<=10^12，N*M<=10^12。
數學問題 組合數 lucas定理
看到那個C的表達式就覺得群組合數有關系，于是歡快地打了個小表，發現——群組合數沒多大關系
以左上角為頂點，每個位置的值以楊輝三角形式增加。根據這一性質可以想出一個貪心方法：隻走直線，先貼着邊走到目标點所在的行/列，然後直走過去。
于是ans=max(n,m)+ Σ C(n+m,d) (1<=d<=min(n,m)) ← C是組合數
題解說後面那個ΣC 就等于C(n+m+1,min(n,m))
看到别的題解寫了lucas定理，自己想了想覺得可以暴力推過去。N*M<=10^12，根據C(n,m)=c(n,n-m)的性質可知公式求組合數最多循環10^6次，可以接受。
确實可以推過去，然而WA了幾個點，原因是這樣算，乘數爆longlong了。
又加了個快速乘就過了。
下附lucas定理寫法：
lucas還是快一點
lucas
本文為部落客原創文章，轉載請注明出處。