Che cos'è esattamente "stamparlo modulo 10^9 + 7" nei siti web di programmazione competitiva?

Nella maggior parte delle competizioni di programmazione, ci viene richiesto di rispondere al risultato in 10^9+7 modulo. La ragione dietro questo è, se i vincoli del problema sono grandi numeri interi, solo algoritmi efficienti possono risolverli in tempo limitato consentito.
Che cosa è l'operazione modulo:
Il resto ottenuto dopo l'operazione di divisione su due operandi è noto come operazione modulo. L'operatore per fare l'operazione modulo è '%'. Per esempio: a % b = c che significa, quando a è diviso per b dà il resto c, 7%2 = 1, 17%3 = 2.
Perché abbiamo bisogno del modulo:

• La ragione di prendere Mod è di prevenire gli overflow interi. Il più grande tipo di dati interi in C/C++ è unsigned long long int che è di 64 bit e può gestire interi da 0 a (2^64 - 1). Ma in alcuni problemi in cui il tasso di crescita dell'output è molto alto, questo alto intervallo di unsigned long long può essere insufficiente.
  Supponiamo che in una variabile a 64 bit 'A', sia memorizzato 2^62 e in un'altra variabile a 64 bit 'B', sia memorizzato 2^63. Quando moltiplichiamo A e B, il sistema non dà un errore di runtime o un'eccezione. Fa solo qualche calcolo fasullo e memorizza il risultato fasullo perché la dimensione del bit del risultato viene dopo la moltiplicazione è troppo grande.
• In alcuni problemi, per calcolare il risultato è necessario il modulo inverso e questo numero aiuta molto perché è primo. Anche questo numero dovrebbe essere abbastanza grande altrimenti le tecniche di inversione modulare potrebbero fallire in alcune situazioni.

A causa di queste ragioni, gli impostatori di problemi richiedono di dare la risposta come risultato del modulo di un certo numero N.
Ci sono alcuni criteri da cui dipende il valore di N:

1. Dovrebbe essere abbastanza grande da rientrare nel più grande tipo di dati interi i.e fa in modo che non ci sia un overflow nel risultato.
2. Dovrebbe essere un numero primo perché se prendiamo mod di un numero per primo il risultato è generalmente distanziato cioè i risultati sono molto diversi rispetto a mod il numero per non primo, ecco perché i primi sono generalmente usati per mod.

10^9+7 soddisfa entrambi i criteri. È il primo numero primo a 10 cifre e si adatta anche al tipo di dati int. Infatti, qualsiasi numero primo inferiore a 2^30 va bene per prevenire possibili overflow.
Come viene usato il modulo:
Alcune proprietà distributive del modulo sono le seguenti:

1. ( a + b) % c = ( ( a % c ) + ( b % c ) ) % c
2. ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
3. ( a - b) % c = ( ( a % c ) - ( b % c ) ) % c
4. ( a / b ) % c = ( ( a % c ) / ( b % c ) ) % c

Quindi, modulo è distributivo su +, * e - ma non su / [Si prega di fare riferimento alla Divisione Modulare per i dettagli]
NOTA: Il risultato di ( a % b ) sarà sempre minore di b.
In the case of computer programs, due to the size of variable limitations, we perform modulo M at each intermediate stage so that range overflow never occurs.

1. Example: 
2. a = 145785635595363569532135132 
3. b = 3151635135413512165131321321 
4. c = 999874455222222200651351351 
5. m = 1000000007 
6. Print (a*b*c)%m. 
7.  
8. Method 1: 
9. First, multiply all the number and then take modulo: 
10. (a*b*c)%m = (459405448184212290893339835148809 
11. 515332440033400818566717735644307024625348601572) %  
12. 1000000007 
13. a*b*c does not fit even in the unsigned long long  
14. int due to which system drop some of its most  
15. significant digits. Therefore, it gives the wrong answer. 
16. (a*b*c)%m = 798848767 
17.  
18. Method 2: 
19. Take modulo at each intermediate steps: 
20. i = 1 
21. i = (i*a) % m // i = 508086243 
22. i = (i*b) % m // i = 144702857 
23. i = (i*c) % m // i = 798848767 
24. i = 798848767  
25.  
26. Method 2 always gives the correct answer.