DP？
Time Limit: 3000ms Memory Limit: 128MB
Description
Figure 1 shows the Yang Hui Triangle. We number the row from top to bottom 0,1,2,…and the column from left to right 0,1,2,….If using C(n,k) rePResents the number of row n, column k. The Yang Hui Triangle has a regular pattern as follows. C(n,0)=C(n,n)=1 (n ≥ 0) C(n,k)=C(n-1,k-1)+C(n-1,k) (0<k<n) Write a program that calculates the minimum sum of numbers passed on a route that starts at the top and ends at row n, column k. Each step can go either straight down or diagonally down to the right like figure 2. As the answer may be very large, you only need to output the answer mod p which is a prime.
Input to the problem will consists of series of up to 100000 data sets. For each data there is a line contains three integers n, k(0<=k<=n<10^9) p(p<10^4 and p is a prime) . Input is terminated by end-of-file.
Output
For every test case, you should output “Case #C: ” first, where C indicates the case number and starts at 1.Then output the minimum sum mod p.
1 1 2 4 2 7
Sample Output
Case #1: 0 Case #2: 5
題目大意
給多個詢問，每次問從楊輝三角的頂點走到(i,j)的路徑上點的最小和%p的值，每次只能向下或右下走。
解題報告
讓j*2小于i,否然C(i,j) = C(i, i-j) 然后發現肯定是先向下走再向右下走最優。 然后又發現C(i,j)+C(i-1,j-1)+….=C(i+1,j), 這個東西可以畫一個楊輝三角出來然后用遞推公式來意識上[滑稽]證明一下。 答案現在等于(n-m)+C(i+1,j) 發現i和j高達10^9那么普通的階乘+逆元肯定是搞不出來的然后看到模數p很小只有10^4就可以使用Lucas(盧卡斯)定理來搞啦^.^ Lucas 定理: 當 
就有 
這種組合一定存在應為這相當于把m,n以p進制表示
現在就可以遞歸地求組合數啦， %p之后的組合數直接階乘+逆元就可以啦 在這里看用快速冪求逆元 擴展歐幾里得也可以并且更快，但是我比較懶嘛。。 還有注意計算組合數一定一定一定要判斷返回值為0的情況啊！
代碼
#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <cmath>int P;int advPow (int a, int b) { if(a == 0) return 0; int ret = 1; while(b) { if(b&1) ret *= a, ret %= P; a *= a; a %= P; b >>= 1; } return ret;}int * fac;int stor[1500][11000], tot;inline int caltC (int n, int m) { if(n<m) return 0; if(n == m || m == 0) return 1; if(n == m+1 || m == 1) return n; return (fac[n]*advPow(fac[m]*fac[n-m]%P, P-2)%P) % P;}int Lucas (int n, int m) { if(n<P && m<P) return caltC(n, m); return caltC(n%P, m%P)*Lucas(n/P, m/P)%P;}int pos[11000];int main () { int n, m, cas = 0; while(~scanf("%d%d%d", &n, &m, &P)) { if(!pos[P]) { pos[P] = ++tot; fac = stor[tot]; fac[1] = 1; for(int i = 2; i<=P; i++) fac[i] = (fac[i-1]*i)%P; } else fac = stor[pos[P]]; if(m*2>n) m = n-m; printf("Case #%d: %d/n", ++cas, ((n-m)+Lucas(n+1, m)) % P); }}
