为了账号安全,请及时绑定邮箱和手机立即绑定

在mod 1000000007问题中需要帮助

在mod 1000000007问题中需要帮助

精慕HU 2019-12-03 16:10:12
我的数学能力很弱,总是陷入那些需要以模素数为模的答案的问题。例如:(500!/ 20!)mod 1000000007我对BigIntegers很熟悉,但是在计算500的阶乘后(甚至在使用DP之后)计算模数似乎要花费大量时间。我想知道是否存在解决此类问题的特殊方法。这是我目前正在尝试解决的一个问题:http : //www.codechef.com/FEB12/problems/WCOUNT如果有人可以引导我学习解决这些编码问题的教程或方法,那将非常有帮助。我熟悉Java和C ++。
查看完整描述

3 回答

?
慕桂英546537

TA贡献1848条经验 获得超10个赞

这些大量模量任务的关键是在执行模量之前不计算全部结果。您应该在中间步骤中减小模数以保持数量小:


500! / 20! = 21 * 22 * 23 * ... * 500


21 * 22 * 23 * 24 * 25 * 26 * 27 = 4475671200


4475671200 mod 1000000007 = 475671172

475671172 * 28 mod 1000000007 = 318792725

318792725 * 29 mod 1000000007 = 244988962

244988962 * 30 mod 1000000007 = 349668811


...


 31768431 * 500 mod 1000000007 = 884215395


500! / 20! mod 1000000007 = 884215395

您无需在每一步都减少模量。只要经常做就足以防止数量过大。


请注意,的最大值long为2 ^ 63-1。因此,在两个正整数值(即其中一个操作数为a long)之间执行64位乘法运算不会溢出long。之后,您可以安全地执行余数运算%(如果也为正数),并在需要时转换为整数。


查看完整回答
反对 回复 2019-12-03
?
哈士奇WWW

TA贡献1799条经验 获得超6个赞

首先,观察一下这500!/20!是21到500之间的所有数字的乘积,包括端点和下一个。接下来,观察您可以逐项执行模乘,%1000000007并在每个运算的末尾进行。您现在应该可以编写程序了。注意不要使数字溢出:32位可能还不够。


查看完整回答
反对 回复 2019-12-03
?
繁星淼淼

TA贡献1775条经验 获得超11个赞

我认为这可能对您有用


for(mod=prime,res=1,i=20;i<501;i++)

{

res*=i; // an obvious step to be done 

if(res>mod) // check if the number exceeds mod

res%=


查看完整回答
反对 回复 2019-12-03
  • 3 回答
  • 0 关注
  • 907 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信