[HDU 3944] DP？组合数 Lucas定理

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

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.

Sample Input

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);
    }
}