Come possiamo computer (N choose K)% M in C o C++ senza richiamare l'overflow?Come possiamo calcolare N scegliere il modulo K un numero primo senza overflow?
Nel caso particolare in cui N (4 < = N < = 1000) eK (1 < = K < = N) e M = 1.000.003.
Per calcolare (n scegliere k)% M, è possibile calcolare separatamente il modulo nominator (n!) M e il modulo denominatore (k! * (N-k)!) M e quindi moltiplicare il nominatore per il denominatore inversione moltiplicativa modulare (in M). Dato che M è primo, puoi usare il piccolo teorema di Fermat per calcolare l'inverso moltiplicativo.
C'è una bella spiegazione, con il codice di esempio, il seguente link (problema SuperSum):
Per una maggiore velocità, calcolare il numeratore come il prodotto da (K + 1) a N e il denominatore come K !. Sappiamo che non ci saranno fattori di M nel calcolo, perché è primo e più grande di N. Quindi possiamo cancellare l'alto e il basso senza preoccuparci che ciò che stiamo cancellando potrebbe essere un multiplo di M (cioè 0). –
Esattamente ho imparato dallo stesso. – Quixotic
Ma ora vedo che 1.000.000,003 non è primo, nessuna idea di come risolvere questo ora? – Quixotic
è possibile utilizzare la formula ricorsiva dal link che hai dato e fare il calcolo mod M.
Usa Stirling's approximation per calcolare il coefficiente binomiale. Quindi calcola il modulo come al solito.
In che modo un'approssimazione aiuta a calcolare il coefficiente binomiale modulo M? Le approssimazioni sono praticamente prive di significato nell'aritmetica modulo. –
Mi dispiace, ho perso la parte di approssimazione. – Quixotic
Ecco un semplice esempio:
(A * B * C) % N ... is equal to... ((A % N) * (B % N) * (C % N)) % N;
Cioè, tutto ciò che serve per applicare il modulo ad ogni operando e di prodotto, o non appena diventa grande un numero. E per ultimo il modulo deve essere applicato al risultato complessivo.
Con 32 bit int può ancora causare un overflow su 1000000000 * 1000. – ybungalobill
@ ybungalobill: applicare '((1000000000% N) * (1000)% N)% N'. – Nawaz
nota che il modulo è M nella domanda, non N, e l'esempio dato, pur non essendo primo, è circa un miliardo. Quindi '1000000000% N' è ancora' 1000000000'. Per evitare l'overflow, è necessario un tipo intero grande come N^2 (ad esempio 'long long' o' int64_t', se disponibile) –
Dal 1000000003 = 23 * 307 * 141623 è possibile calcolare (n Choses k) mod 23 , 307 e 141623 e quindi applicare il teorema del promemoria cinese [1]. Quando si calcola n !, k! e (n-k)!, dovresti calcolare ogni 23 mod 30, 307 e 141623 ogni fase per prevenire l'overflow.
In questo modo è necessario evitare l'overflow anche in macchine a 32 bit.
Un piccolo miglioramento sarebbe quello di calcolare (n choses k) mod 141623 e 7061 (23 * 307) (modifica: ma può essere un po 'complicato calcolare il modulo inverso 7061, quindi non lo farei)
Mi dispiace per il mio inglese scarso.
[1] http://en.wikipedia.org/wiki/Chinese_remainder_theorem
Edit2: Un altro potenzialmente problema che ho trovato è il calcolo n! mod 23 (per esempio) sarà probabilmente 0, ma ciò non implica che (n choses k) sia 0 mod 23, quindi dovresti contare quante volte 23 divide n !, (n-k)! e k! prima di calcolare (n sceglie k). Calcolare questo è facile, p divide n! esattamente piano (n/p) + piano (n/p²) + ... volte. Se succede che 23 divide n! le stesse volte in cui divide k! e (nk) !, procedete a calcolare (n choses k) mod 23 dividendo per 23 ogni multipler di esso ogni volta. Lo stesso vale per 307, ma non per 141623
Per i primi piccoli, 23 e 307, è possibile utilizzare http://en.wikipedia.org/wiki/Lucas%27_theorem invece di contare i poteri. –
Sembra essere stato [già risposto altrove] (http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690) –