I wrote the theory of combinatorial calculation using Fermat's little theorem and an implementation example of java. It also includes an implementation example of speeding up by pre-calculation, which is used when calculating combinations multiple times. The implementation example can be used for general purposes by pasting it in the source.
** How to find the combination $ _nC_r $ **
This is done using Pascal's triangle. It can be calculated up to n = 4000. I wrote the idea and implementation example in here. However, even if n is small, if mod can be calculated as a method, it may be calculated using Fermat's little theorem as when n is large.
The combination when n is large is calculated under the method of a large prime number mod. When mod is applied, n! And r! Can be calculated without overflowing, so it can be calculated according to the following formula.
nCr=\frac{n!}{r!{(n-r)!}}
However, since division cannot be performed freely in mod calculation, it can be solved by transforming it into multiplication using Fermat's little theorem.
{\displaystyle a^{p-2}\equiv a^{-1}{\pmod {p}}} //Fermat's Little Theorem
For $ r! $, The following transformation can be made under the method p by using the above equation.
\frac{1}{r!} = (r!)^{p-2}
Therefore, $ _nC_r $ can be calculated as follows under the law p.
nCr=\frac{n!}{r!{(n-r)!}}=n! (r!)^{p-2}((n-r)!)^{p-2}
The constant name used as the law is mod on the source. (100_000_007 etc. are given from the problem.) Factorial calculation is a method called modpow, which is accelerated by the iterative square method. In addition, the formula is slightly modified as follows (same as when calculating manually).
nCr=\frac{n(n-1)(n-2)\cdots(n-r+1)}{r(r-1)(r-2)\cdots 2*1}
Combination calculation using Fermat's little theorem
//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; //molecule
long div = 1; //denominator
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; //Calculated by multiplication using Fermat's Little Theorem
return ans;
}
//Fast pow under mod conditions
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;
}
Usage example
Usage example
public static void main(String[] args) {
System.out.println(fermatComb(5, 2)); //Calculate 5C2->Output 10
System.out.println(fermatComb(50000, 3000)); //Calculate 50000C3000->Output 890850597(1e9+Residual divided by 7)
}
The worst complexity of the above combination calculation is $ O (nlog (mod)) $, When performing repetitive combination calculations, it may not be possible to meet the time limit if calculated each time. For example, in the following problem, TLE is performed when the combination calculation is performed n times. ABC-E - Max-Min Sums
As a solution in such a case, you can speed up the combination calculation to $ O (log (mod)) $ by calculating the factorial to be used in combination with $ O (N) $ in advance. I will.
Accelerated combination calculation with pre-calculation
//Fast Fermat Combination
static int mod = (int) 1e9 + 7;
static long factorials[]; //An array that stores the result of factorial calculation in advance
static void pre_factorials(int n) { //0!〜n!Ask for
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;
}
//Fast pow under mod conditions
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;
}
How to Use
Usage example
public static void main(String[] args) {
int n = 1_000_000; //n=Suppose you want up to 1 million
pre_factorials(n); //1!From n!Prepare an array with values up to
System.out.println(fastFermatComb(5, 2)); //Calculate 5C2->Output 10
System.out.println(fastFermatComb(50000, 3000)); //Calculate 50000C3000->Output 890850597(1e9+Residual divided by 7)
}
In fact, it can be made even faster, and the pre-calculation can be O (N) and the combination calculation can be O (1).
In Speed Up 1, by calculating the factorial in advance, the pre-calculation could be accelerated to O (N) and the combination calculation to O (log (mod)), but the log of O (log (mod)) Since (mod) is based on division, it is possible to speed up to O (1) by calculating the factorial division in advance.
Since $ log (mod) = log (10 ^ 9 + 7) = 29.90 $, When performing combination calculation n times, it becomes O (nlog (mod)), and the time limit becomes strict at about $ n = 10 ^ 6 $. For example, the following problem cannot be solved without speeding up to O (1). ABC154-F Many Many Paths
Pre-calculate factorial division
//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];//Array to store the result of 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]);//First 1/(n!)By asking for 1/(n-1)!It can be calculated by multiplication from.
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;
}
that's all. The above code uses the following modulo calculation library for simplicity.
mod calculation library
//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;
}