Rapide n choisir k mod p pour n grand?

Ce que je veux dire par "grand n" est quelque chose dans les millions. p est premier.

J'ai essayé
http://apps.topcoder.com/wiki/display/tc/SRM+467
Mais la fonction semble incorrect (je l'ai testé avec 144 choisir 6 mod 5 et il me donne 0 quand il doit me donner 2)

J'ai essayé
http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690
Mais je ne comprends pas pleinement

J'ai aussi fait un memoized fonction récursive qui utilise la logique (combinaisons(n-1, k-1, p)%p + combinaisons(n-1, k, p)%p), mais il me donne un débordement de pile problèmes parce que n est grand

J'ai essayé Théorème de Lucas, mais elle semble être lente ou inexactes.

Tout ce que je suis en train de faire est de créer un rapide/précis n choisir k mod p pour n grand. Si quelqu'un pouvait aider à me montrer une bonne mise en œuvre pour cela, je serais très reconnaissant. Merci.

Comme demandé, le memoized version qui frappe les débordements de pile pour n grand:

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;
   }  
}
  • avez-vous besoin de connaître précisément le rappel ou suffit-il de savoir si le nombre est également divisible par p? (n choisir k mod p == 0)
  • Pas sûr de comprendre la question. La réponse à la n de choisir k mod p doit être exact/exact.
  • ce qui ne les combinaisons de retour de la fonction(pourquoi faut-il prendre 3 arguments)
  • les combinaisons de la fonction prend trois arguments, car c'est de trouver (n choisir k) mod p
  • Si vous avez besoin de calculer la combinaison(n, k)%p?
  • Est-ce devoirs?
  • post une version récursive, quelqu'un peut peut-être vous aider à transformer en une solution itérative en évitant les stackoverflow exception
  • Non, @dbaupp, il n'est pas de devoirs.
  • La solution sur TopCoder fonctionne pour p > n.

InformationsquelleAutor John Smith | 2012-04-12