2015
04-14

# DP?

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

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

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

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

p同余

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

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

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