Hai bisogno di aiuto in mod 1000000007 domande

Question

Sono debole in matematica e sono sempre bloccato con i problemi che richiedono la risposta modulo un numero primo.

ad esempio: (!! 500/20) mod 1.000.000,007 mila

Sono a conoscenza BigIntegers ma calcolo modulo dopo il calcolo fattoriale di 500 (anche dopo aver utilizzato DP) sembra prendere un sacco di tempo.

Mi piacerebbe sapere se c'è un modo particolare di affrontare/affrontare questo tipo di problemi.

Qui è uno di questi problema che sto cercando di risolvere in questo momento: http://www.codechef.com/FEB12/problems/WCOUNT

Sarebbe veramente utile se qualcuno mi potrebbe dirigere ad un tutorial o un approccio per gestire questi problemi di codifica. Ho familiarità con Java e C++.

Answer 1

La chiave per questi compiti modulo di grande numero non è calcolare il risultato completo prima di eseguire il modulo. si dovrebbe ridurre il modulo nei passaggi intermedi per mantenere il numero piccolo:

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 

Non è necessario per ridurre il modulo ad ogni singolo passo. Fallo abbastanza spesso per evitare che il numero diventi troppo grande.

---

noti che il valore massimo di long è 2^63 - 1. Quindi eseguire moltiplicazioni 64 bit tra due valori interi positivi (cioè uno degli operandi è un long) non traboccherà long. È possibile eseguire in tutta sicurezza l'operazione rimanente % in seguito (se ciò è positivo) e tornare a un numero intero quando richiesto.

Answer 2

Iniziare osservando che 500!/20! è il prodotto di tutti i numeri da 21 a 500 inclusi e Avanti, osservare che è possibile eseguire la moltiplicazione modulo voce per articolo, prendendo %1000000007 alla fine di ogni operazione. Dovresti essere in grado di scrivere il tuo programma ora. Fare attenzione a non traboccare il numero: 32 bit potrebbero non essere sufficienti.

Answer 3

credo che questo potrebbe essere di qualche utilità per voi

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 
}