求组合数

1. 范围较小. 求 ,共n组询问。 1 ≤ n ≤ 10000, 1 ≤ b ≤ a ≤ 2000

暴力使用杨辉三角即可。f[i][j] = f[i - 1][j - 1] + f[i - 1][j]

 

2. 仍求第一问的值,但是1 ≤ b ≤ a ≤ ,预处理出的逆元和阶乘展开即可。

 

3. ,共n组询问。1 ≤ n ≤ 20, 1 ≤ b ≤ a ≤ ,1 ≤ p ≤  (eg:hdu3944)

Lucas定理 :

故时间复杂度为

(1)为递归

(2)为计算每次组合数的时候最多P次

(3)为每次快速幂的次数

全部评论

相关推荐

notbeentak...:就抓,嗯抓,开不开匿名都要抓,一点坏事不让说,就对公司顶礼膜拜佩服的五体投地就对了
点赞 评论 收藏
分享
专业嗎喽:个人信息名字太大,合到电话邮箱那一栏就行,有党员写过党,剩下其他全删,站空太大了 把实习经历丰富,放最前面,然后是个人评价,技能之类的,然后是学校信息。项目经历最后面,可以就选一个自己擅长的。 现在是学校不是92就扣分的,没必要放前面。 然后现在看重实习经历>竞赛经历(校园经历)>课程项目经历
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务