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.
Vous devez vous connecter pour publier un commentaire.
Alors, voici comment vous pouvez résoudre votre problème.
Bien sûr, vous connaissez la formule:
(Voir http://en.wikipedia.org/wiki/Binomial_coefficient#Computing_the_value_of_binomial_coefficients)
Vous savez comment faire pour calculer le numérateur:
Maintenant, comme p est premier la réciproque de chaque entier qui est premiers avec p est bien définie, c'est à dire un-1 peut être trouvé. Et cela peut être fait à l'aide de Fermat a(p-1)=1(mod p) => a*a(p-2)=1(mod p) et donc un-1=a(p-2).
Maintenant tout que vous devez faire est de mettre en œuvre rapide de l'exponentiation(par exemple à l'aide de la méthode binaire):
Et maintenant vous pouvez ajouter le dénominateur de notre résultat:
Veuillez noter que je suis en utilisant de longs partout pour éviter le type de débordement. Bien sûr, vous n'avez pas besoin de faire
k
exponentiations - vous pouvez calculer k!(mod p) et ensuite de diviser une seule fois:EDIT: comme par @dbaupp commentaire si k >= p k! sera égal à 0 modulo p et (k!)^-1 ne sera pas défini. Pour éviter que d'abord calculer le degré avec lequel p est dans n*(n-1)...(n-k+1) et k! et de les comparer:
EDIT: Il y a un plus d'optimisation qui peut être ajouté à la solution ci - dessus au lieu de le calcul de l'inverse du nombre de chaque multiple de k!, on peut calculer k!(mod p) et ensuite calculer l'inverse de ce nombre. Ainsi, nous avons à payer le logarithme de l'exponentiation qu'une seule fois. Bien sûr, nous avons encore à jeter le p diviseurs de chaque multiple. Nous n'avons qu'à changer la dernière boucle avec ceci:
n*(n-1)*...*(n-k+1) * (k!)^-1
? Ce n'est définie que sik < p
, sinonk! == 0
et n'inverse existe.Pour les grandes
k
, nous pouvons réduire le travail de manière significative en exploitant deux faits fondamentaux:Si
p
est un nombre premier, l'exposant dep
dans le premier factorisation den!
est donnée par(n - s_p(n)) /(p-1)
, oùs_p(n)
est la somme des chiffres den
dans la basep
représentation (donc pourp = 2
, c'est popcount). Ainsi, l'exposant dep
dans le premier factorisation dechoose(n,k)
est(s_p(k) + s_p(n-k) - s_p(n)) /(p-1)
, en particulier, qu'il est nul si et seulement si le plusk + (n-k)
a pas de report lorsqu'elle est effectuée dans la base dep
(l'exposant est le nombre de porte).Le théorème de Wilson:
p
est un nombre premier si et seulement si(p-1)! ≡ (-1) (mod p)
.L'exposant de
p
dans la factorisation den!
est généralement calculée parLa vérification de la divisibilité de
choose(n,k)
parp
n'est pas strictement nécessaire, mais il est raisonnable d'avoir que la première, puisqu'elle sera souvent le cas, et puis c'est moins de travail:Maintenant, laissez-nous jeter un oeil de plus près à
n!
. Nous avons séparé les numéros de≤ n
dans les multiples dep
et les nombres premiers entre eux àp
. AvecLes multiples de
p
contribuerp^q * q!
. Les nombres premiers entre eux àp
contribuer le produit de(j*p + k), 1 ≤ k < p
pour0 ≤ j < q
, et le produit de(q*p + k), 1 ≤ k ≤ r
.Pour les nombres premiers entre eux à
p
nous ne sera intéressé à la contribution modulop
. Chaque de la pleine pistesj*p + k, 1 ≤ k < p
est conforme à(p-1)!
modulop
, donc, tout à fait, ils produisent une contribution de(-1)^q
modulop
. La dernière (peut-être) incomplète exécuter produitr!
modulop
.Donc, si nous écrire
nous obtenons
où
cop(m,r)
est le produit de tous les nombres premiers entre eux àp
qui sont≤ m*p + r
.Il y a deux possibilités,
a = b + c
etA = B + C
, oua = b + c + 1
etA = B + C - p
.Dans notre calcul, nous avons éliminé le deuxième au préalable de la possibilité, mais qui n'est pas essentiel.
Dans le premier cas, l'explicite pouvoirs de
p
annuler, et nous nous retrouvons avecTous les pouvoirs de
p
divisantchoose(n,k)
viennent dechoose(a,b)
- dans notre cas, il n'y en aura pas, puisque nous avons éliminé ces cas avant et, bien quecop(a,A) /(cop(b,B) * cop(c,C))
n'a pas besoin d'être un nombre entier (considérer par exemplechoose(19,9) (mod 5)
), lorsque l'on considère l'expression modulop
,cop(m,r)
réduit à(-1)^m * r!
, de sorte que, depuisa = b + c
, le(-1)
annuler et nous nous retrouvons avecDans le second cas, nous trouvons
depuis
a = b + c + 1
. Le report dans le dernier chiffre signifie queA < B
, donc, modulop
(où l'on peut remplacer la division avec une multiplication par l'inverse modulaire, ou de la considérer comme une congruence de nombres rationnels, ce qui signifie le numérateur est divisible par
p
). De toute façon, nous constatons de nouveauMaintenant, nous pouvons reproduire pour la
choose(a,b)
partie.Exemple:
Désormais la mise en œuvre:
Pour calculer l'inverse modulaire, vous pouvez utiliser de Fermat est (soi-disant peu) le théorème de
et de calculer l'inverse de ce que
a^(p-2) (mod p)
, ou d'utiliser une méthode applicable à un large éventail d'arguments, l'algorithme d'Euclide étendu ou en fraction continue d'extension, qui vous donnent l'inverse modulaire pour toute paire de premiers entre eux (positive) des entiers:Comme le calcul de
a^(p-2) (mod p)
, c'est unO(log p)
algorithme, pour certains intrants, c'est nettement plus rapide (c'est en faitO(min(log k, log p))
, pour les petitsk
et grandp
, il est nettement plus rapide), pour d'autres c'est plus lent.Dans l'ensemble, de cette façon, nous avons besoin de calculer au plus O(log_p k) des coefficients binomiaux modulo
p
, où chaque coefficient binomial besoins au plus O(p) de l'exploitation, ce qui donne une complexité de O(p*log_p k) opérations.Lorsque
k
est nettement plus grande quep
, qui est beaucoup mieux que leO(k)
solution. Pourk <= p
, il se réduit à laO(k)
solution avec des frais généraux.