Was ich mit "großes n" meine, ist etwas in den Millionen. p ist prime.

ich habe es versuchthttp://apps.topcoder.com/wiki/display/tc/SRM+467 Aber die Funktion scheint falsch zu sein (ich habe es mit 144 getestet, wähle 6 Mod 5 und es gibt mir 0, wenn es mir 2 geben sollte)

ich habe es versuchthttp://online-judge.uva.es/board/viewtopic.php?f=22&t=42690 Aber ich verstehe es nicht ganz

Ich habe auch eine auswendig gelernte rekursive Funktion erstellt, die die Logik verwendet (Kombinationen (n-1, k-1, p)% p + Kombinationen (n-1, k, p)% p), aber es gibt mir Stapelüberlaufprobleme, weil n ist groß

Ich habe Lucas Theorem ausprobiert, aber es scheint entweder langsam oder ungenau zu sein.

Ich versuche nur, ein schnelles / genaues n zu erstellen, wähle k mod p für großes n. Wenn mir jemand dabei helfen könnte, eine gute Implementierung zu zeigen, wäre ich sehr dankbar. Vielen Dank.

Wie angefordert, läuft die gespeicherte Version, die auf den Stapel trifft, für ein großes n über:

<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>