Быстрое n выбирает k по модулю p для больших n?

То, что я имею в виду под «большим n», исчисляется миллионами. p — простое число.

Я пытался 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 велико

Я попробовал использовать теорему Лукаса, но она оказалась либо медленной, либо неточной.

Все, что я пытаюсь сделать, это создать быстрый/точный n, выбирающий k по модулю p для больших n. Если кто-нибудь может помочь показать мне хорошую реализацию для этого, я был бы очень благодарен. Спасибо.

В соответствии с запросом, запомненная версия, которая вызывает переполнение стека для больших n:

std::map, 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, 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;
   }  
}