|
Titlul: Numarul lui Catalan Scris de: George Popoiu din Martie 31, 2010, 17:41:26 Nu stiu cum pot calcula numarul lui catalan pentru numere foarte mari. n<=11000 . Este o problema pe campion care cere rezultatul modulo 44711, iar daca aplic modulo pe parcurs ce calculez, imi da un rezultat gresit.
Eu stiu urmatoarele relatii : C(n) = Comb(2n,n) / n+1 C(n) = Comb(2n,n) - Comb(2n,n-1) C(n) = [ (4n+2)/(n+2) ] * C(n-1), unde C(0)=C(1)=1 Se poate calcula fara sa implementez operatii pe numere mari ? PS : problema se numeste 'fotbal' . Titlul: Răspuns: Numarul lui Catalan Scris de: Dragos-Alin Rotaru din Martie 31, 2010, 17:44:29 Da, se poate calcula fara a implementa pe numere mari. Aplici Inversul modular (http://infoarena.ro/problema/inversmodular).
|