【题意】：给出一个杨辉三角，问从最左上角到第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