【題意】：給出一個楊輝三角，問從最左上角到第n行第k列的一條路徑中，所經過的數值和最小是多少。路徑需滿足當前的位置只能移動到它下方的第一個數或正對角線的第一個數。

【題解】：一開始以為是個dp，發現n,k都很大，肯定是數學題了。
               很容易發現楊輝三角具有對稱性，所以我們只需要研究k <= n / 2的情況。
               利用貪心思想，每次都往左上方轉移直到去到第0列，然后最后全部往上轉移直到最上方。
               容易得出公式：
                     ans = C(n, k) + C(n-1, k-1) + …… + C(n-k+1, 1) + C(n-k, 0) + n - k
                           把 C(n-k, 0) 換成 C(n-k+1, 0)，由公式 C(n, k) = C(n-1, k) + C(n-1, k-1) 可以進行化簡
               化簡后得：
                     ans = C(n+1, k) + n - k

                     推出答案我很開心，以為接下來就沒了，可是我發現n很大，普通求組合數會TLE，逼于無奈，我搜了一下，發現了Lucas定理。
                     至于什么是Lucas定理，大家自己百度吧。
                     用了定理剛開始還是TLE，因為case高達10W，還要打表記下模每個素數的階乘，最后終于過了。

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 using namespace std;
12 #define pb push_back
13 #define lc(x) (x << 1)
14 #define rc(x) (x << 1 | 1)
15 #define lowbit(x) (x & (-x))
16 #define ll long long
17 #define maxp 10050
18 ll n, k, p;
19 ll fac[maxp][1500];
20 int prime[maxp], hash[maxp];
21 bool visit[maxp];
22 
23 void init() {
24     memset(visit, false, sizeof(visit));
25     int tot = 0;
26     prime[tot] = 2, hash[2] = tot, tot++;
27     for(int i = 3; i < maxp; i += 2) {
28         if(!visit[i]) {
29             prime[tot] = i, hash[i] = tot, tot++;
30             if(i * i < maxp)
31                 for(int j = 2 * i; j < maxp; j += i) visit[j] = true;
32         }
33     }
34     for(int i = 0; i < tot; i++) {
35         fac[0][i] = 1;
36         for(int j = 1; j < maxp; j++) {
37             fac[j][i] = (fac[j-1][i] * j) % prime[i];
38         }
39     }
40 }
41 
42 ll quickpower(ll x, ll n) {
43     ll res = 1;
44     x %= p;
45     while(n) {
46         if(n & 1) res = res * x % p;
47         x = x * x % p;
48         n >>= 1;
49     }
50     return res;
51 }
52 
53 ll C(ll n, ll k, ll p) {
54     ll res = 1;
55     if(k > n) return 0;
56     res = fac[n][hash[p]] * quickpower(fac[n-k][hash[p]] * fac[k][hash[p]], p - 2) % p;
57     return res;
58 }
59 
60 ll Lucas(ll n, ll k, ll p) {
61     if(k == 0) return 1;
62     return C(n % p, k % p, p) * Lucas(n / p, k / p, p) % p;
63 }
64 
65 int main() {
66     int Case = 1;
67     init();
68     while(~scanf("%lld%lld%lld", &n, &k, &p)) {
69         if(k > n / 2) k = n - k;
70         ll ans = (Lucas(n+1, k, p) + n - k) % p;
71         printf("Case #%d: %lld\n", Case++, ans);
72     }
73     return 0;
74 }
75