Rápido n elegir k mod p para n grande?
Lo que quiero decir con "n grande" es algo en millones. p es primo
He intentadohttp://apps.topcoder.com/wiki/display/tc/SRM+467 Pero la función parece ser incorrecta (lo probé con 144 escogí 6 mod 5 y me da 0 cuando debería darme 2)
He intentadohttp://online-judge.uva.es/board/viewtopic.php?f=22&t=42690 Pero no lo entiendo completamente.
También hice una función recursiva memoized que usa la lógica (combinaciones (n-1, k-1, p)% p + combinaciones (n-1, k, p)% p) pero me da problemas de desbordamiento de pila porque n es grande
He intentado el teorema de Lucas pero parece ser lento o inexacto.
Todo lo que estoy tratando de hacer es crear una n precisa / rápida para elegir k mod p para n grande. Si alguien pudiera ayudarme a mostrarme una buena implementación para esto, estaría muy agradecido. Gracias.
Según lo solicitado, la versión memoized que golpea los desbordamientos de pila 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>