Szybko n wybierz k mod p dla dużych n?
Co mam na myśli przez „duże n” to coś w milionach. p jest pierwszym.
próbowałemhttp://apps.topcoder.com/wiki/display/tc/SRM+467 Ale funkcja wydaje się być niepoprawna (przetestowałem ją ze 144, wybierz 6 mod 5 i daje mi 0, gdy powinien dać mi 2)
próbowałemhttp://online-judge.uva.es/board/viewtopic.php?f=22&t=42690 Ale nie rozumiem tego w pełni
Zrobiłem też zapamiętaną funkcję rekurencyjną, która używa logiki (kombinacje (n-1, k-1, p)% p + kombinacje (n-1, k, p)% p), ale daje mi to problemy z przepełnieniem stosu, ponieważ n jest duży
Próbowałem twierdzenia Lucas'a, ale wydaje się, że jest albo wolny, albo niedokładny.
Wszystko, co próbuję zrobić, to stworzyć szybki / dokładny n wybrać k mod p dla dużego n. Gdyby ktoś mógł mi pokazać dobre wdrożenie, byłbym bardzo wdzięczny. Dzięki.
Zgodnie z żądaniem, zapamiętana wersja, która uderza w stos przepełnia się dla dużego n:
<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>