Calcul du Coefficient Binomial (nCk) pour les grandes n & k
je viens de voir cette question et n'ont aucune idée de comment le résoudre. pouvez-vous me fournir des algorithmes , des codes C++ ou des idées?
C'est très simple problème. Étant donné la valeur de N et K, vous DEVEZ nous dire la valeur du coefficient binomial C(N,K). Vous pouvez être assuré que K < = N et la valeur maximale de N est de 1.000.000.000.000.000. Puisque la valeur peut être très grande, vous devez calculer le résultat modulo 1009. D'entrée
La première ligne de l'entrée contient le nombre de cas d'essai T, au plus 1000. Chacune des lignes suivantes de T se compose de deux entiers séparés par l'espace N et K, où 0 <= K <= N et 1 <= N <= 1,000,000,000,000,000. Sortie
pour chaque cas d'essai, imprimer sur une nouvelle ligne, la valeur du coefficient binomial C(N,K) modulo 1009. Exemple
Entrée:
3
3 1
5 2
10 3Sortie:
3
10
120
5 réponses
notez que 1009 est une prime.
Maintenant, vous pouvez utiliser Le Théorème De Lucas.
qui dit:
Let p be a prime.
If n = a1a2...ar when written in base p and
if k = b1b2...br when written in base p
(pad with zeroes if required)
Then
(n choose k) modulo p = (a1 choose b1) * (a2 choose b2) * ... * (ar choose br) modulo p.
i.e. remainder of n choose k when divided by p is same as the remainder of
the product (a1 choose b1) * .... * (ar choose br) when divided by p.
Note: if bi > ai then ai choose bi is 0.
ainsi votre problème se réduit à trouver le produit modulo 1009 d'au plus log n / log 1009 nombres (nombre de chiffres de N dans la base 1009) de la forme a choisir b où a <= 1009 et b <= 1009.
cela devrait le rendre plus facile même lorsque N est proche de 10^15.
Remarque:
Pour N=10^15, N choisir N / 2 est plus que 2^(100000000000000) ce qui est au-delà d'un long non signé.
aussi, l'algorithme suggéré par Le théorème de Lucas est o (log n) Qui est
exponentiallyplus rapide que d'essayer de calculer le coefficient binomial directement (même si vous avez un mod 1009 pour prendre soin du problème de débordement).
voici un peu de code pour Binomial que j'avais écrit il y a longtemps, tout ce que vous devez faire est de le modifier pour faire les opérations modulo 1009 (Il pourrait y avoir bugs et pas forcément recommandé style de codage):
class Binomial
{
public:
Binomial(int Max)
{
max = Max+1;
table = new unsigned int * [max]();
for (int i=0; i < max; i++)
{
table[i] = new unsigned int[max]();
for (int j = 0; j < max; j++)
{
table[i][j] = 0;
}
}
}
~Binomial()
{
for (int i =0; i < max; i++)
{
delete table[i];
}
delete table;
}
unsigned int Choose(unsigned int n, unsigned int k);
private:
bool Contains(unsigned int n, unsigned int k);
int max;
unsigned int **table;
};
unsigned int Binomial::Choose(unsigned int n, unsigned int k)
{
if (n < k) return 0;
if (k == 0 || n==1 ) return 1;
if (n==2 && k==1) return 2;
if (n==2 && k==2) return 1;
if (n==k) return 1;
if (Contains(n,k))
{
return table[n][k];
}
table[n][k] = Choose(n-1,k) + Choose(n-1,k-1);
return table[n][k];
}
bool Binomial::Contains(unsigned int n, unsigned int k)
{
if (table[n][k] == 0)
{
return false;
}
return true;
}
le coefficient Binomial est un factoriel divisé par deux autres, bien que le k! terme sur le fond annule de façon évidente.
observez que si 1009, (y compris les multiples de celui-ci), apparaît plus de fois dans le numérateur que le dénominateur, alors la réponse mod 1009 est 0. Il ne peut pas apparaître plus de fois dans le dénominateur que le numérateur (puisque les coefficients binomiaux sont des entiers), donc les seuls cas où vous devez faire quelque chose sont quand il apparaît le même nombre de de fois en fois. N'oubliez pas de compter les multiples de (1009)^2 comme deux, et ainsi de suite.
après cela, je pense que vous nettoyez juste de petits cas (ce qui signifie un petit nombre de valeurs à multiplier/diviser), bien que je ne suis pas sûr sans quelques tests. Sur le côté plus 1009 est premier, donc arithmétique modulo 1009 a lieu dans un champ, ce qui signifie qu'après avoir jeté des multiples de 1009 à la fois de haut et de bas, vous pouvez faire le reste de la multiplication et division mod 1009 dans n'importe quel ordre.
là où il reste des cas non petits, il faudra quand même multiplier ensemble de longues séries d'entiers consécutifs. Cela peut être simplifié en sachant 1008! (mod 1009). Il est -1 (1008 si vous préférez), depuis 1 ... 1008 sont les p-1 non nulle éléments du premier champ sur p. Par conséquent ils se composent de 1, -1, et puis (p-3)/2 paires d'inverses multiplicatives.
Donc par exemple, considérons le cas de C((1009^3), 200).
Imaginez que le nombre des 1009s sont égaux (Je ne sais pas s'ils le sont, parce que je n'ai pas codé de formule pour le savoir), de sorte que c'est un cas nécessitant du travail.
Sur le dessus, nous avons 201 ... 1008, que nous devrons calculer ou chercher dans une table prédéfinie, puis 1009, puis 1010 ... 2017, 2018, 2019 ... 3026, 3027, etc. Le. .. les plages sont toutes -1, donc nous avons juste besoin de savoir comment beaucoup de ces plages.
il reste 1009, 2018, 3027, qu'une fois que nous les aurons annulés avec 1009 de la le bas sera juste 1, 2, 3,... 1008, 1010, ..., plus quelques multiples de 1009^2, que nous annulerons et nous laisserons avec des entiers consécutifs à multiplier.
Nous pouvons faire quelque chose de très similaire avec le bas pour calculer le produit mod 1009 "1 ... 1009^3-200 avec tous les pouvoirs de 1009 divisés sur". Cela nous laisse avec une division dans un premier champ. IIRC c'est délicat en principe, mais 1009 est un nombre assez petit pour que nous puissions en Gérer 1000 (la limite supérieure sur le nombre de cas de test).
bien sûr avec k = 200, Il y a un énorme chevauchement qui pourrait être annulé plus directement. C'est ce que je voulais dire par petits cas et non-petits cas: je l'ai traité comme un non-Petit cas, alors qu'en fait nous pourrions nous en tirer avec juste "brute-forçant" celui-ci, en calculant ((1009^3-199) * ... * 1009^3) / 200!
je ne pense pas que vous voulez calculer C(n,k), puis à les réduire mod 1009. Le plus grand, C (1e15,5e14) aura besoin de quelque chose comme 1e16 bits ~ 1000 teraoctets
en outre, l'exécution de la boucle dans snakiles réponse 1e15 fois semble que cela pourrait prendre un certain temps. Ce que vous pourriez utiliser est, si
n = n0 + n1*p + n2*p^2 ... + nd*p^d
m = m0 + m1*p + m2*p^2 ... + md*p^d
(où 0< = mi, ni < p)
puis C(n,m) = C(n0,m0) * C (N1,m1) *... * C (nd, nd) mod p
voir, par exemple,http://www.cecm.sfu.ca/organics/papers/granville/paper/binomial/html/binomial.html
une façon serait d'utiliser le triangle de pascal pour construire une table de tous les C(m,n) pour 0<=m<=n<=1009.
code psudo pour le calcul de nCk:
result = 1
for i=1 to min{K,N-K}:
result *= N-i+1
result /= i
return result
complexité temporelle: O (min{K, N-K})
La boucle va from i=1 to min{K,N-K} au lieu de from i=1 to K, et c'est ok parce que
C(k,n) = C(k, n-k)
et vous pouvez calculer la chose encore plus efficacement si vous utilisez la fonction GammaLn.
nCk = exp(GammaLn(n+1)-GammaLn(k+1)-GammaLn(n-k+1))
la fonction GammaLn est le logarithme naturel du fonction Gamma. Je sais qu'il y a un algorithme efficace pour calculer la fonction GammaLn mais l'algorithme n'est pas trivial du tout.
Le code suivant montre comment obtenir tous les coefficients binomiaux pour une taille donnée 'n'. Vous pouvez facilement le modifier pour l'arrêter à un k donné afin de déterminer nCk. Il est mathématiquement très efficace, il est simple de code, et travaille pour de très grandes de n et k.
binomial_coefficient = 1
output(binomial_coefficient)
col = 0
n = 5
do while col < n
binomial_coefficient = binomial_coefficient * (n + 1 - (col + 1)) / (col + 1)
output(binomial_coefficient)
col = col + 1
loop
1
1 * (5 + 1 - (0 + 1)) / (0 + 1) = 5
5 * (5 + 1 - (1 + 1)) / (1 + 1) = 15
15 * (5 + 1 - (2 + 1)) / (2 + 1) = 15
15 * (5 + 1 - (3 + 1)) / (3 + 1) = 5
5 * (5 + 1 - (4 + 1)) / (4 + 1) = 1
j'avais trouvé la formule une fois sur Wikipédia, mais pour une raison quelconque, il n'est plus là :(