好难的题目啊,是cantalon数的一般情况啊,公式为c(a+b,b)-c(a+b,b-1),一开始想从cantalon推这一题,白浪费了一个小时,又是打了m,n的表和组合数的表,才推了这公式
写完提交后无限WA,直到练习赛时间过了才想起来是我求的com(a+b, b)-com(a+b,b-1)可能为负值,因为a>b不代表a%p>b%p,即(a-b)%p
= ((a%p-b%p)+p)%p而不是a%p-b%p,贴个临时的代码,好像代码有点冗长,再修改修改。(已修改)
time:1718ms
删了a,b,c三个数组,其它也有调整了一下,快了一倍
time:812ms
刚刚发现计算com(a+b,b)与com(a+b,b-1)几乎是重复计算了一次,果断改之(也避免了(a-b)%c小于0的问题!)
直接计算com(a+b,b)-com(a+b,b-1)=(a+b)!(n+1-m)/(m!(n+1)!) 注意!不要计算ans=(a+b)!/(m!(n+1)!),再计算ans*(n+1-m),因为不能保证(a+b)!/(m!(n+1)!)可以整除!
time:421MS
发现有15 ms,32ms过的,若哪位大仙知道,求赐教啊!
刚刚找到的公式的推导:
参考自:http://apps.hi.baidu.com/share/detail/17473477
①:我们设初始在坐标系的原点(0,0),从字符串第一位开始,碰到一个1就向上走,碰到一个0就向右走,那么由n个1、m个0组成的字符串最后必定走到(n,m)点,即满足由n个1、m个0组成的字符串的个数为C(n+m,n) = C(n+m,m) (满足n+m长度内n个长度走1或者m个长度走0)。
②:对于任意前缀中1的个数不少于0的个数的字符串的个数这个条件,可以看成是坐标系中,从(0,0)点走到(m, n)点,并且跟y=x-1这条直线不相交的方案数。又因为(0,0)点关于直线y=x-1的对称点是(1,-1),而从(1,-1)点走到(m, n)点的所有方案一定都会与直线y=x-1相交,对于这些方案,将从(1,-1)点到与y=x-1的第一个交点之间的路径关于y=x-1对称翻转过去,就可以得到所有不满足题意的从(0,0)点走到(m, n)点的方案,于是最终答案就是C(n+m, n)-C(n+m,n+1)。
第一点一开始就看出来了,第二点的转化才是关键的啊
分享到:
相关推荐
the problem solved with hdu 3398~
HDU最全ac代码
hdu2000-2014ac代码,虽然只有几道,但都是简单的
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
hdu2101AC代码
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
HDU_ACM培训课件(完整版) HDU_ACM培训课件(完整版) HDU_ACM培训课件(完整版) HDU_ACM培训课件(完整版)
自己做的HDU ACM已经AC的题目
hdu 一些简单题目 ac代码 大概100道
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
hdu杭电所有题目按照ac数量排序,python分析
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
ACM hdu 代码大全3000例,hdu已经AC的3000例代码,部分代码有详细解析
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门