我所说的"大n"是数以百万计的东西.p是素数.
我已经尝试了 http://apps.topcoder.com/wiki/display/tc/SRM+467 但是这个功能似乎是不正确的(我用144选择6 mod 5测试了它,当它应该给我时它给了我0 2)
我试过 http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690 但我完全不明白
我还做了一个memoized递归函数,它使用逻辑(组合(n-1,k-1,p)%p +组合(n-1,k,p)%p)但是它给了我堆栈溢出问题因为n很大
我尝试过卢卡斯定理,但它似乎要么缓慢还是不准确.
我所要做的就是为大n创建一个快速/准确的n选择k mod p.如果有人能帮我展示一个很好的实现,我将非常感激.谢谢.
根据要求,对于大n的命中堆栈溢出的memoized版本:
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 …