首页 > ACM题库 > HDU-杭电 > HDU 3944-DP? -数论-[解题报告]HOJ
2015
04-14

HDU 3944-DP? -数论-[解题报告]HOJ

DP?

问题描述 :

K-th Nya Number

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.

输出:

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.

样例输入:

1 1 2
4 2 7

样例输出:

Case #1: 0
Case #2: 5

原题连接:http://acm.hdu.edu.cn/showproblem.php?pid=3944

题目大意:求杨辉三角中从塔尖到n行k列所经过的路径中,虽经过数字之和最小的一条路

经过观察,很容易想到的一个结论就是,这个最小值是从定点开始,然后到合适的位置45度斜着走到(n,k)的位置,也就是

//c(m,n) 表示n中选m个

c(0,n-k)+c(1,n-k+1)+c(2,n-k+2) + …… + c(k,n) + n – k;

现在的关键就是求前面的那些组合数的和的公式

当时,我并不知道c(0,n-k)+c(1,n-k+1)+c(2,n-k+2) + …… + c(k,n) 的公式

然后我就用组合数学的式子证明了,c(0,n-k)+c(1,n-k+1)+c(2,n-k+2) + …… + c(k,n)  = c(k,n+1)

证明过程如下:

有G{c(k,n+k)} = 1 / (1-x)^(n+1);这个是组合数学里面关于生成函数的式子

现在我们有:G{c(m,n-k+m)} = 1 / (1-x)^(n-k+1)

即:c(m,n-l+m) 的生成函数是  A(x) = 1 / (1-x)^(n-k+1);

令:B(x) = A(0) + A(1) + A(2) +…..+A(x)

则:B(x) = A(x)/(1-x) = 1 / (1 – k)^(n-k+2); //这个是生成函数的一个重要性质

再次使用G{c(k,n+k)} = 1 / (1-x)^(n+1)

就可以求得:B(x) = G{c(k,n – k+1)} 所以B(x)的第k项的系数为c(k,n+1)


我原以为这个到这儿就要结束了,总结上面的就是,结果为 (c(k,n+1)+n-k) modp

哎,我刚刚学习数学啊,还是太幼稚了

由于n和k的值都很大,也就是说,求c(k,n+1)的时候还是一个很大的麻烦,怎么求呢??

这儿就有了一个 Lucas定理

定理是这样的:

A、B是非负整数,p是质数。AB写成p进制:A=a[n]a[n-1]…a[0],B=b[n]b[n-1]…b[0]。

则组合数C(A,B)与C(a[n],b[n])*C(a[n-1],b[n-1])*…*C(a[0],b[0])  mod
p同余

Lucas定理的证明用到了数论的知识,我的数论还在起步的状态,我没有看懂!

然后就是求组合数连乘了

但是当我敲进了一个模板的时候,tle,我傻眼了,原来这个题需要预处理一下,因为,这儿的数据规模太大了

下面的东西,我看的那个解题报告我没看懂,包含的内容如下:筛素数,素数阶乘模逆    好像是这样的,我由于数论还没有看多少,没看懂


我是第一次推导这样的公式,如有不妥的地方,还望多多交流

贴一个代码吧:

#include <cstdio>
#include <cstring>
#include <vector>
#define maxn 10000
using namespace std;
int flag[maxn],pim[maxn],tol;
int p[1229][9973];
int ni[1229][9973];
int mp[10000];
void init()
{
    tol=0;
    for(int i=2; i<maxn; i++) //素数筛
    {
        if(!flag[i])  pim[tol++]=i;
        for(int j=0; j<tol&&i*pim[j]<maxn; j++)
        {
            flag[i*pim[j]]=1;
            if(i%pim[j]==0) break;
        }
    }
    for(int i=0; i<tol; i++) //对每一个素数求各阶乘模和逆
    {
        int k=pim[i];
        mp[k]=i;
        p[i][0]=1, p[i][1]=1;
        ni[i][0]=1,ni[i][1]=1;
        for(int j=2; j<k; j++) //从2!到(p-1)!
        {
            p[i][j]=j*p[i][j-1]%pim[i];
            ni[i][j]=-k/j*ni[i][k%j]%k;
            if(ni[i][j]<0) ni[i][j]+=k;
        }
    }
    for(int i=0; i<tol; i++) //求阶乘逆
    {
        int k=pim[i];
        for(int j=1; j<k; j++)
        {
            ni[i][j]=ni[i][j]*ni[i][j-1]%k;
        }
    }
}
int cal(int n,int m,int v)
{
    if(n<m) return 0;
    int x=mp[v];
    return p[x][n] * ni[x][m]%v * ni[x][n-m]%v;
}
int main()
{
    int n,k,p,ca=0;
    init();
    while(scanf("%d %d %d",&n,&k,&p)==3)
    {
        if(k>n/2) k=n-k;
        int res=1,u_u=n-k;
        n++;
        while(n&&k)
        {
            res=res*cal(n%p,k%p,p)%p;
            if(res==0) break;
            n/=p;
            k/=p;
        }
        printf("Case #%d: %d\n",++ca,(res+u_u)%p);
    }
    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/wukonwukon/article/details/6897136


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。