Быстро n выбрать k mod p для больших n?
Что я имею в виду под "большим n" это что-то в миллионах. р простое.
Я пытался http://apps.topcoder.com/wiki/display/tc/SRM+467 Но функция кажется неправильной (я проверил это с 144 выберите 6 мод 5, и он дает мне 0, когда он должен дать мне 2)
Я пытался http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690 Но я не понимаю этого полностью
Я также сделал запомненную рекурсивную функцию, которая использует логику (комбинации (n-1, k-1, p)% p + комбинации (n-1, k, p)% p), но это дает мне проблемы переполнения стека, потому что п большой
Я пробовал теорему Лукаса, но она кажется медленной или неточной.
Все, что я пытаюсь сделать, - это создать быстрый / точный n, выбрать k mod p для больших n. Если бы кто-нибудь мог помочь показать мне хорошую реализацию для этого, я был бы очень благодарен. Благодарю.
В соответствии с запросом запомненная версия, которая попадает в переполнение стека для больших 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>