J'ai écrit la théorie du calcul de combinaison en utilisant le théorème de Fermat et un exemple d'implémentation de java. Il comprend également un exemple de mise en œuvre de l'accélération par pré-calcul, qui est utilisé lors du calcul de combinaisons plusieurs fois. L'exemple d'implémentation peut être collé dans la source et utilisé à des fins générales.
** Comment trouver la combinaison $ _nC_r $ **
Ceci est fait en utilisant le triangle de Pascal. Il peut être calculé jusqu'à n = 4000. J'ai écrit l'idée et l'exemple de mise en œuvre dans ici. Cependant, même si n est petit, si mod peut être calculé comme une méthode, il peut être calculé en utilisant le petit théorème de Fermat comme dans le cas d'un grand n.
La combinaison lorsque n est grand est calculée selon la méthode d'un grand premier mod. Lorsque mod est appliqué, n! Et r! Peuvent être calculés sans débordement, donc ils peuvent être calculés selon la formule suivante.
nCr=\frac{n!}{r!{(n-r)!}}
Cependant, comme la division ne peut pas être effectuée librement dans le calcul mod, elle peut être résolue en la transformant en multiplication en utilisant le théorème de Fermat.
{\displaystyle a^{p-2}\equiv a^{-1}{\pmod {p}}} //Théorème de Fermat
Pour $ r! $, La transformation suivante peut être effectuée selon la méthode p en utilisant l'équation ci-dessus.
\frac{1}{r!} = (r!)^{p-2}
Par conséquent, $ _nC_r $ peut être calculé comme suit selon la méthode p.
nCr=\frac{n!}{r!{(n-r)!}}=n! (r!)^{p-2}((n-r)!)^{p-2}
Le nom de la constante utilisé comme loi est mod sur la source. (100_000_007 etc. sont donnés à partir du problème.) Le calcul du plancher est une méthode appelée modpow, qui est accélérée par la méthode itérative du carré. De plus, la formule est légèrement modifiée comme suit (comme lors du calcul manuel).
nCr=\frac{n(n-1)(n-2)\cdots(n-r+1)}{r(r-1)(r-2)\cdots 2*1}
Calcul combiné utilisant le théorème de Fermat
//Fermat Combination
static int mod = (int) 1e9 + 7;
static long fermatComb(long a, long b) {
if (b > a - b)
return fermatComb(a, a - b);
long mul = 1; //molécule
long div = 1; //dénominateur
for (int i = 0; i < b; i++) {
mul *= (a - i);
mul %= mod;
div *= (i + 1);
div %= mod;
}
long ans = mul * modpow(div, mod - 2) % mod; //Calculé par multiplication à l'aide du théorème de Fermat
return ans;
}
//Rapide pow dans des conditions mod
static long modpow(long a, long p) {
if (p == 0)
return 1;
if (p % 2 == 0) {
long root = modpow(a, p / 2);
return root * root % mod;
} else
return a * modpow(a, p - 1) % mod;
}
Exemple d'utilisation
Exemple d'utilisation
public static void main(String[] args) {
System.out.println(fermatComb(5, 2)); //Calculer 5C2->Sortie 10
System.out.println(fermatComb(50000, 3000)); //Calculer 50000C3000->Sortie 890850597(1e9+Résiduel divisé par 7)
}
Le pire montant de calcul du calcul de combinaison ci-dessus est $ O (nlog (mod)) $, Lors de l'exécution de calculs de combinaison répétitifs, il peut ne pas être possible de respecter le délai s'il est calculé à chaque fois. Par exemple, dans le problème suivant, TLE est effectué lorsque le calcul de combinaison est effectué n fois. ABC-E - Max-Min Sums
Comme solution dans un tel cas, vous pouvez accélérer le calcul de la combinaison à $ O (log (mod)) $ en calculant à l'avance le facteur de multiplication qui peut être utilisé en combinaison avec $ O (N) $. Je vais.
Calcul de combinaison accéléré avec pré-calcul
//Fast Fermat Combination
static int mod = (int) 1e9 + 7;
static long factorials[]; //Un tableau qui stocke le résultat du calcul de multiplication à l'avance
static void pre_factorials(int n) { //0!〜n!Demander
factorials = new long[n + 1];
factorials[0] = 1;
for (int i = 0; i < n; i++) {
factorials[i + 1] = (long)(i + 1) * factorials[i] % mod;
}
}
static long fastFermatComb(long a, long b) {
if (factorials.length == 0)
System.err.println("error : factorials has not been culculated!! do [pre_factorials] method");
long af = factorials[(int) a];
long bf = factorials[(int) b];
long abf = factorials[(int) (a - b)];
long res = af * modpow(bf, mod - 2) % mod * modpow(abf, mod - 2) % mod;
return res;
}
//Rapide pow dans des conditions mod
static long modpow(long a, long p) {
if (p == 0)
return 1;
if (p % 2 == 0) {
long root = modpow(a, p / 2);
return root * root % mod;
} else
return a * modpow(a, p - 1) % mod;
}
Comment utiliser
Exemple d'utilisation
public static void main(String[] args) {
int n = 1_000_000; //n=Supposons que vous vouliez jusqu'à 1 million
pre_factorials(n); //1!De n!Préparez un tableau avec des valeurs allant jusqu'à
System.out.println(fastFermatComb(5, 2)); //Calculer 5C2->Sortie 10
System.out.println(fastFermatComb(50000, 3000)); //Calculer 50000C3000->Sortie 890850597(1e9+Résiduel divisé par 7)
}
En fait, cela peut être fait encore plus rapidement, et le pré-calcul peut être O (N) et le calcul de combinaison peut être O (1).
Dans Speed Up 1, en calculant la puissance à l'avance, le pré-calcul pourrait être accéléré à O (N) et le calcul de combinaison à O (log (mod)), mais le log de O (log (mod)) Puisque (mod) est basé sur la division, il est possible d'accélérer jusqu'à O (1) en pré-calculant la division du plancher.
Puisque $ log (mod) = log (10 ^ 9 + 7) = 29,90 $, Lorsque le calcul de combinaison est effectué n fois, il devient O (nlog (mod)), et la limite de temps devient stricte à environ $ n = 10 ^ 6 $. Par exemple, le problème suivant ne sera pas dans le temps à moins qu'il ne soit accéléré à O (1). ABC154-F Many Many Paths
Pré-calculer la division du sol
//Fast Fermat Combination
static long factorials[];
static long factorialDivs[];
static void pre_factrials(int n) {
factorials = new long[n + 1];
factorialDivs = new long[n + 1];//Un tableau qui stocke le résultat de la division
factorials[0] = 1;
for (int i = 0; i < n; i++) {
factorials[i + 1] = mul(i + 1, factorials[i]);
}
factorialDivs[n] = div(1, factorials[n]);//Premier 1/(n!)En demandant 1/(n-1)!Il peut être calculé par multiplication à partir de.
for (int i = n - 1; i >= 0; i--) {
factorialDivs[i] = mul(factorialDivs[i + 1], i + 1);
}
}
static long fastFermatComb(int a, int b) {
if (factorials.length == 0)
System.err.println("error : factorials has not been culculated!! do [pre_factorial] method");
long af = factorials[a];
long bf = factorialDivs[b];
long abf = factorialDivs[a - b];
long res = mul(mul(af, bf), abf);
return res;
}
c'est tout. Le code ci-dessus utilise la bibliothèque de calcul de mod suivante pour plus de simplicité.
bibliothèque de calcul mod
//MOD culculations
static long plus(long x, long y) {
x %= mod;
y %= mod;
long res = (x + y) % mod;
return res;
}
static long sub(long x, long y) {
x %= mod;
y %= mod;
long res = (x - y + mod) % mod;
return res;
}
static long mul(long x, long y) {
x %= mod;
y %= mod;
long res = x * y % mod;
return res;
}
static long div(long x, long y) {
x %= mod;
y %= mod;
long res = x * modpow(y, mod - 2) % mod;
return res;
}
static long modpow(long a, long p) {
if (p == 0)
return 1;
if (p % 2 == 0) {
long halfP = p / 2;
long root = modpow(a, halfP);
return root * root % mod;
} else
return a * modpow(a, p - 1) % mod;
}