需要帮助在mod 1000000007问题
我的math能力很弱，总是遇到需要回答模数的问题。
例如：（500！/ 20！）mod 1000000007
我熟悉BigInteger，但计算500的阶乘（甚至在使用DP之后）计算模似乎花费了大量的时间。
我想知道是否有一个特定的方法来处理这类问题。
这是我正在尝试解决的一个这样的问题： http : //www.codechef.com/FEB12/problems/WCOUNT
如果有人能够指导我编写一个教程或一个方法来处理这些编码问题，那真的很有帮助。 我熟悉Java和C ++。
这些大数模量任务的关键不是在执行模数之前计算完整结果。 你应该减less在中间步骤的模数，以保持数字小：
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。因此，在两个正整数值（即其中一个操作数很long ）之间执行64位乘法不会溢出long 。 您可以安全地执行余下的操作% （如果这也是肯定的），并在需要时转换回整数。
开始观察500!/20! 是从21到500的所有数字的乘积，其中，观察可以逐项执行模乘，在每次操作结束时取%1000000007 。 你现在应该可以编写你的程序了。 小心不要溢出数字：32位可能不够。
我认为这可能对你有一些用处
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%=mod; // so as to avoid the modulo as it is costly operation }
