我的數學能力很弱，總是陷入那些需要以模素數為模的答案的問題。例如：（500！/ 20?。﹎od 1000000007我對BigIntegers很熟悉，但是在計算500的階乘后（甚至在使用DP之后）計算模數似乎要花費大量時間。我想知道是否存在解決此類問題的特殊方法。這是我目前正在嘗試解決的一個問題：http : //www.codechef.com/FEB12/problems/WCOUNT如果有人可以引導我學習解決這些編碼問題的教程或方法，那將非常有幫助。我熟悉Java和C ++。
3 回答
慕桂英546537
TA貢獻1848條經驗 獲得超10個贊
這些大量模量任務的關鍵是在執行模量之前不計算全部結果。您應該在中間步驟中減小模數以保持數量?。?/p>
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。之后，您可以安全地執行余數運算%（如果也為正數），并在需要時轉換為整數。
哈士奇WWW
TA貢獻1799條經驗 獲得超6個贊
首先，觀察一下這500!/20!是21到500之間的所有數字的乘積，包括端點和下一個。接下來，觀察您可以逐項執行模乘，%1000000007并在每個運算的末尾進行。您現在應該可以編寫程序了。注意不要使數字溢出：32位可能還不夠。
繁星淼淼
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%=
添加回答
舉報
0/150
提交
取消