https://codeforces.com/contest/893/problem/E
Solution where C(n,m) does not cross the boundary but A(n,m) crosses the boundary
C(n,m) = A(n,m) / (n-m)!
This question requires modulo 1e9 + 7, but only addition, subtraction, and multiplication can modulate it, but division cannot. Therefore, this A(n,m) needs to store the original value. The original value is too large and becomes long long.
It would be nice if there could be no division and all multiplication
Method 1: Split into multiple prime numbers and multiply them
First count how many 2 3 5 7 there are in A(n,m), then subtract the number of 2 3 5 7 in (n-m)!, and finally multiply the remaining ones
long long C(int n, int m){<!-- -->
long long ret=1;
unordered_map<int,int> table;
for(int x=n;x>m;x--){<!-- -->
int tmpx=x;
for(int i=2;i<=tmpx;i + + ){<!-- -->
if(tmpx%i==0){<!-- -->
int tmpcnt=1;
tmpx=tmpx/i;
while(tmpx%i==0 & amp; & amp; tmpx){<!-- -->
tmpcnt++;
tmpx/=i;
}
table[i] + =tmpcnt;
}
}
}
for(int x=n-m;x>=1;x--){<!-- -->
int tmpx=x;
for(int i=2;i<=tmpx;i + + ){<!-- -->
if(tmpx%i==0){<!-- -->
int tmpcnt=1;
tmpx=tmpx/i;
while(tmpx%i==0 & amp; & amp; tmpx){<!-- -->
tmpcnt++;
tmpx/=i;
}
table[i]-=tmpcnt;
}
}
}
for(auto it=table.begin(); it!=table.end();it + + ){<!-- -->
int x=it->first;
int cnt=it->second;
ret=(ret*quickpower(cnt, x))%MOD;
}
return ret%MOD;
}
Method 2: Division to Multiplication
A
/
B
(
m
o
d
M
)
≡
A
?
B
M
?
2
(
m
o
d
M
)
A/B \pmod{M} ≡ A*B^{M-2} \pmod {M}
A/B(modM)≡A?BM?2(modM)
Fermat’s Little Theorem: If M is a prime number, and B and M are mutually prime, then B^(M-1) mod M = 1
M itself is a prime number, and of course it is coprime with B.
A/B mod M
= A/B mod M * 1
= A/B mod M * B^(M-1) mod M
= A*B^(M-2) mod M
Theory: Inverse Element
Inverse element: bx ≡ 1 (mod M), x is said to be the inverse element of a mod M
(a / b) mod M = a * x mod M
(a / b) mod M
= (a / b) * 1 mod M
= (a / b) * (b * x) mod M
= a * x mod M
And the value of x(inv(b)): x ≡ b^{M-2} (mod M)
because
b
x
≡
1
(
m
o
d
M
)
bx \equiv 1 \pmod M
bx≡1(modM);
sob
x
≡
b
M
?
1
(
m
o
d
M
)
bx \equiv b^{M-1} \pmod M
bx≡bM?1(modM) (according to Fermat’s little theorem);
sox
≡
b
M
?
2
(
m
o
d
M
)
x \equiv b^{M-2} \pmod M
x≡bM?2(modM).
C(n,m) template
C(n,m) mod M
= n! / m! / (n-m)! mod M
= n! * inv(m!) * inv((n-m)!) mod M
// f factorial, inv inverse element
long long f[MAXN],inv[MAXN];
long long quickpower(long long a, long long b){<!-- -->...}
void init()
{<!-- -->
f[0]=inv[0]=1;
for(long long i=1; i<maxn; i + + )
{<!-- -->
f[i]=f[i-1]*i%MOD;
inv[i]=quickpower(f[i], MOD-2);
}
}
long long C(long long n, long long m)
{<!-- -->
return f[n] * inv[n-m]%MOD * inv[m]%MOD;
}
Binomial Theorem
C
(
n
,
0
)
+
C
(
n
,
1
)
+
C
(
n
,
2
)
+
.
.
.
+
C
(
n
,
n
)
=
2
n
C(n,0) + C(n,1) + C(n,2) + … + C(n,n) = 2^n
C(n,0) + C(n,1) + C(n,2) + … + C(n,n)=2n
(1 + x)^n, assign x a value of 1
C
(
n
,
1
)
+
C
(
n
,
3
)
+
C
(
n
,
5
)
+
.
.
.
=
2
n
?
1
C(n,1) + C(n,3) + C(n,5) + … = 2^{n-1}
C(n,1) + C(n,3) + C(n,5) + …=2n?1
C
(
n
,
0
)
+
C
(
n
,
2
)
+
C
(
n
,
4
)
+
.
.
.
=
2
n
?
1
C(n,0) + C(n,2) + C(n,4) + … = 2^{n-1}
C(n,0) + C(n,2) + C(n,4) + …=2n?1
(1 + x)^n, assign value to x as -1
“memset”: identifier not found
#include<string.h>