Rápido n escolha k mod p para n grande?
O que quero dizer com "n grande" é algo na casa dos milhões. p é primo.
eu tenteihttp://apps.topcoder.com/wiki/display/tc/SRM+467 Mas a função parece estar incorreta (eu testei com 144 escolha 6 mod 5 e me dá 0 quando deveria me dar 2)
eu tenteihttp://online-judge.uva.es/board/viewtopic.php?f=22&t=42690 Mas eu não entendo isso completamente
Eu também fiz uma função recursiva memoizada que usa a lógica (combinações (n-1, k-1, p)% p + combinações (n-1, k, p)% p) mas isso me dá problemas de estouro de pilha porque n é grande
Eu tentei Lucas Theorem mas parece ser lento ou impreciso.
Tudo o que estou tentando fazer é criar um rápido / preciso n escolher k mod p para n grande. Se alguém pudesse ajudar a me mostrar uma boa implementação para isso eu ficaria muito grato. Obrigado.
Conforme solicitado, a versão memoizada que atinge os overflows de pilha para n grande:
<code>std::map<std::pair<long long, long long>, long long> memo; long long combinations(long long n, long long k, long long p){ if (n < k) return 0; if (0 == n) return 0; if (0 == k) return 1; if (n == k) return 1; if (1 == k) return n; map<std::pair<long long, long long>, long long>::iterator it; if((it = memo.find(std::make_pair(n, k))) != memo.end()) { return it->second; } else { long long value = (combinations(n-1, k-1,p)%p + combinations(n-1, k,p)%p)%p; memo.insert(std::make_pair(std::make_pair(n, k), value)); return value; } } </code>