`
lilisalo
  • 浏览: 1102119 次
文章分类
社区版块
存档分类
最新评论

HDU/HDOJ 3944 DP? 多校联合11 电子科大 lucas定理

 
阅读更多

DP?

Time Limit: 10000/3000 MS (Java/Others)Memory Limit: 128000/128000 K (Java/Others)
Total Submission(s): 637Accepted Submission(s): 239


Problem 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

Author
phyxnj@UESTC

Source
这个题的想法还是比较明确,要让值最小,那么必然就是要让1走的尽可能多,所以路线必然是尽可能的走最边上的1
分析一下:
显然第 n 行第 k 列的数就是组合数 C(n,k) ,答案满足对称性。只需要讨论k<=n/2的
情况。考虑从目的地往上走到顶点,因为组合数在k<=n/2是递增的,所以每次只要斜向上
走,到了最左端,再往上走就可以得到最小的和,所以最小的和为
C(n,k)+C(n-1,k-1)+C(n-2,k-2)+……+C(n-k,0)+n-k;
用C(n-k+1,0)替换掉C(n-k,0)后,得到:
C(n-k+1,0)+C(n-k+1,1)+C(n-k+2,2)+……+C(n-1,k-1)+C(n,k)+n-k
对于组合数有C(n,k)=C(n-1,k-1)+C(n-1,k)
所以最左边两个数相加得 C(n-k+2,1),继续与 C(n-k+2,2)相加得到 C(n-k+3,2),一直加下
去最后得到C(n+1,k)。
所以最小的和为C(n+1,k)+n-k。
紧接着,就是计算C(n+1,k)对p去模了,这个需要用到lucas定理。
而且还要预处理
我的代码:

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics