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
Sample Output
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定理。
而且还要预处理
我的代码:
分享到:
相关推荐
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
2017hdu多校联合训练第一场标程及数据
HDU的一题........HDU DP动态规
ACM/ICPC 2010年多校联合第十场第九题的解题报告及代码,AC代码有三个,最好的是src
hdoj的一些题目分类,由hdu大牛搜集,希望对做ac的同志们有帮助
HDU2013暑期多校联合训练第一场0723-解题报告和标程
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
这份压缩包内包含了2019年杭电多校第一场的数据与标程,欢迎下载
Hdu 1020解题报告,http://acm.hdu.edu.cn/showproblem.php?pid=1020
hdoj 2013 多校训练3标程+解题报告
自己积累的部分杭电oj的(hdu)解题代码。。大家有空来看看。 基本上是自己写的哈。有错误之处请指教、
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间...
2014 Multi-University Training Contest 1多校联合赛标程和部分数据。
杭电oj4405,一道简单的概率dp题目
flutter_web_browser 一个flutter插件,可使用和打开网页。 此插件正在开发中,API可能会更改。入门安装从pub安装库: dependencies: flutter_web_browser: "^0.14.0"导入库import 'package:flutter_web_browser/...
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
http://acm.hdu.edu.cn/showproblem.php?pid=2020 绝对值排序 txt格式
ACM ICPC HDOJ1000
动态规划DP题解 POJ HDU部分动态规划DP题解
杭电acm解题报告 详细解析2000-2099 适合acm初学者