Ich habe die Theorie der Kombinationsberechnung unter Verwendung des Satzes von Fermat und eines Implementierungsbeispiels von Java geschrieben. Es enthält auch ein Implementierungsbeispiel für die Beschleunigung durch Vorberechnung, das bei der mehrfachen Berechnung von Kombinationen verwendet wird. Das Implementierungsbeispiel kann in die Quelle eingefügt und für allgemeine Zwecke verwendet werden.
** So finden Sie die Kombination $ _nC_r $ **
Dies geschieht mit Pascals Dreieck. Es kann bis zu n = 4000 berechnet werden. Ich habe die Idee und das Implementierungsbeispiel in [hier] geschrieben (https://qiita.com/naru7sh/items/7f3f47fbf2e415c0ec86). Selbst wenn n klein ist und mod als Methode berechnet werden kann, kann es unter Verwendung des kleinen Satzes von Fermat wie im Fall von großem n berechnet werden.
Die Kombination, wenn n groß ist, wird nach der Methode eines großen Primmods berechnet. Wenn mod angewendet wird, können n! Und r! Ohne Überlaufen berechnet werden, sodass es gemäß der folgenden Formel berechnet werden kann.
nCr=\frac{n!}{r!{(n-r)!}}
Da die Division in der Mod-Berechnung nicht frei durchgeführt werden kann, kann sie gelöst werden, indem sie unter Verwendung des Fermat-Theorems in eine Multiplikation umgewandelt wird.
{\displaystyle a^{p-2}\equiv a^{-1}{\pmod {p}}} //Satz von Fermat
Für $ r! $ Kann die folgende Transformation unter Verwendung der obigen Gleichung unter der Methode p durchgeführt werden.
\frac{1}{r!} = (r!)^{p-2}
Daher kann $ _nC_r $ unter der Methode p wie folgt berechnet werden.
nCr=\frac{n!}{r!{(n-r)!}}=n! (r!)^{p-2}((n-r)!)^{p-2}
Der als Gesetz verwendete konstante Name ist mod auf der Quelle. (100_000_007 usw. ergeben sich aus dem Problem.) Die Bodenberechnung ist eine Methode namens Modpow, die durch die iterative Quadratmethode beschleunigt wird. Darüber hinaus wird die Formel wie folgt geringfügig geändert (wie bei der manuellen Berechnung).
nCr=\frac{n(n-1)(n-2)\cdots(n-r+1)}{r(r-1)(r-2)\cdots 2*1}
Kombinationsberechnung nach dem Satz von 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; //Molekül
long div = 1; //Nenner
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; //Berechnet durch Multiplikation nach dem Satz von Fermat
return ans;
}
//Schnelle Leistung unter Mod-Bedingungen
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;
}
Anwendungsbeispiel
Anwendungsbeispiel
public static void main(String[] args) {
System.out.println(fermatComb(5, 2)); //Berechnen Sie 5C2->Ausgabe 10
System.out.println(fermatComb(50000, 3000)); //Berechnen Sie 50000C3000->Ausgabe 890850597(1e9+Rest geteilt durch 7)
}
Der schlechteste Berechnungsbetrag der obigen Kombinationsberechnung ist $ O (nlog (mod)) $, Bei wiederholten Kombinationsberechnungen kann das Zeitlimit möglicherweise nicht eingehalten werden, wenn es jedes Mal berechnet wird. In dem folgenden Problem wird beispielsweise TLE ausgeführt, wenn die Kombinationsberechnung n-mal durchgeführt wird. ABC-E - Max-Min Sums
Als Lösung in einem solchen Fall können Sie die Kombinationsberechnung auf $ O (log (mod)) $ beschleunigen, indem Sie im Voraus den Multiplikationsfaktor berechnen, der in Kombination mit $ O (N) $ verwendet werden kann. Ich werde.
Beschleunigte Kombinationsberechnung mit Vorberechnung
//Fast Fermat Combination
static int mod = (int) 1e9 + 7;
static long factorials[]; //Ein Array, das das Ergebnis der Multiplikationsberechnung im Voraus speichert
static void pre_factorials(int n) { //0!〜n!Nachfragen
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;
}
//Schnelle Leistung unter Mod-Bedingungen
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;
}
Wie benutzt man
Anwendungsbeispiel
public static void main(String[] args) {
int n = 1_000_000; //n=Angenommen, Sie möchten bis zu 1 Million
pre_factorials(n); //1!Von n!Bereiten Sie ein Array mit Werten bis zu vor
System.out.println(fastFermatComb(5, 2)); //Berechnen Sie 5C2->Ausgabe 10
System.out.println(fastFermatComb(50000, 3000)); //Berechnen Sie 50000C3000->Ausgabe 890850597(1e9+Rest geteilt durch 7)
}
Tatsächlich kann es sogar noch schneller gemacht werden, und die Vorberechnung kann O (N) und die Kombinationsberechnung O (1) sein.
In Speed Up 1 könnte durch Vorberechnung der Leistung im Voraus die Vorberechnung auf O (N) und die Kombinationsberechnung auf O (log (mod)) beschleunigt werden, aber das Protokoll von O (log (mod)) Da (mod) auf Division basiert, ist es möglich, auf O (1) zu beschleunigen, indem die Division des Bodens im Voraus berechnet wird.
Da $ log (mod) = log (10 ^ 9 + 7) = 29,90 $, Wenn die Kombinationsberechnung n-mal durchgeführt wird, wird sie zu O (nlog (mod)), und das Zeitlimit wird bei ungefähr $ n = 10 ^ 6 $ streng. Zum Beispiel kann das folgende Problem nicht gelöst werden, ohne auf O (1) zu beschleunigen. ABC154-F Many Many Paths
Berechnen Sie die Aufteilung des Bodens vor
//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];//Ein Array, das das Ergebnis der Division speichert
factorials[0] = 1;
for (int i = 0; i < n; i++) {
factorials[i + 1] = mul(i + 1, factorials[i]);
}
factorialDivs[n] = div(1, factorials[n]);//Erste 1/(n!)Indem Sie nach 1 fragen/(n-1)!Sie kann durch Multiplikation von berechnet werden.
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;
}
das ist alles. Der obige Code verwendet der Einfachheit halber die folgende Mod-Berechnungsbibliothek.
Mod Berechnungsbibliothek
//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;
}