本介绍主要是在学习后写下自己的理解，故以转载形式发出。
题意： 给定
n
,
m
,
p
n,m,p
n,m,p，求
C
n
m
m
o
d
p
C_n^m\mod p
Cnmmodp，其中
1
≤
m
≤
n
≤
1
0
18
,
2
≤
p
≤
1
0
6
1\leq m\leq n\leq 10^{18},2\leq p\leq 10^6
1≤m≤n≤1018,2≤p≤106。
题解：
- 目标：求
C
n
m
m
o
d
p
C_n^m\mod p
Cnmmodp
- 对
p
p
p分解质因数：
p
=
p
1
α
1
p
2
α
2
p
3
α
3
…
p=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\dots
p=p1α1p2α2p3α3…
- 联想到中国剩余定理，
p
k
α
k
p_k^{\alpha_k}
pkαk是互质的模数，设
x
=
C
n
m
m
o
d
p
x=C_n^m\mod p
x=Cnmmodp，所以有：
{
C
n
m
(
m
o
d
p
1
α
1
)
C
n
m
(
m
o
d
p
2
α
2
)
.
.
.
\left\{\begin{array}{l} C_n^m \pmod {p_{1}^{\alpha_1}}\\ C_n^m \pmod {p_{2}^{\alpha_2}}\\ ...\\ \end{array}\right.
⎩⎨⎧Cnm(modp1α1)Cnm(modp2α2)...
答案
x
x
x就是合并所有同余式得到的答案。
-
问题转换为了：
C
n
m
m
o
d
P
k
,
[
p
∈
p
r
i
m
e
s
]
C_n^{m} \mod P^k,[p\in primes]
CnmmodPk,[p∈primes]
即：
n
!
m
!
(
n
−
m
)
!
m
o
d
P
k
\frac{n!}{m!(n-m)!}\mod P^k
m!(n−m)!n!modPk
那么问题就是无法确定
n
!
n!
n!中的
P
P
P是否对取模
P
k
P^k
Pk有影响，以及如何求出
m
!
,
(
n
−
m
)
!
m!,(n-m)!
m!,(n−m)!的逆元。由于
a
a
a对
p
p
p存在逆元的条件是
g
c
d
(
a
,
p
)
=
1
gcd(a,p)=1
gcd(a,p)=1
所以先将
P
P
P从中提出：
n
!
P
x
m
!
P
y
(
n
−
m
)
!
P
z
P
x
−
y
−
z
m
o
d
P
k
\frac{\frac{n!}{P^x}}{\frac{m!}{P^y}\frac{(n-m)!}{P^z}}P^{x-y-z}\mod P^k
Pym!Pz(n−m)!Pxn!Px−y−zmodPk
-
显然求出
n
!
P
x
\frac{n!}{P^x}
Pxn!即可。
-
对
n
!
n!
n!变形：
n
!
=
1
⋅
2
⋅
3
⋅
.
.
.
⋅
n
=
(
P
⋅
2
P
⋅
3
P
.
.
.
)
(
1
⋅
2...
)
n!=1\cdot2\cdot 3 \cdot ...\cdot n=(P\cdot 2P\cdot 3P...)(1\cdot2...)
n!=1⋅2⋅3⋅...⋅n=(P⋅2P⋅3P...)(1⋅2...)
=
P
⌊
n
P
⌋
(
1
⋅
2
⋅
.
.
.
⋅
⌊
n
P
⌋
)
(
1
⋅
2...
)
\ \ \ \ \ = P^{\lfloor \frac{n}{P} \rfloor}(1\cdot2\cdot...\cdot\lfloor \frac{n}{P} \rfloor)(1\cdot2...)
=P⌊Pn⌋(1⋅2⋅...⋅⌊Pn⌋)(1⋅2...)
=
P
⌊
n
P
⌋
(
⌊
n
P
⌋
)
!
∏
n
i
=
1
,
(
i
m
o
d
P
≠
0
)
i
\ \ \ \ \ = P^{\lfloor \frac{n}{P} \rfloor}(\lfloor \frac{n}{P} \rfloor)! \underset{i=1,(i \ mod\ P \neq0)}{\overset{n}{\prod}}i
=P⌊Pn⌋(⌊Pn⌋)!i=1,(i mod P=0)∏ni
显然，后面这个连乘式是具有循环节的，且最后会有一段不完整的部分，这个部分长度也可能为
0
0
0。
即：
P
⌊
n
P
⌋
(
⌊
n
P
⌋
)
!
(
∏
P
k
i
=
1
,
(
i
m
o
d
P
≠
0
)
i
)
⌊
n
P
k
⌋
(
∏
n
i
=
P
k
⌊
n
P
k
⌋
,
(
i
m
o
d
P
≠
0
)
i
)
P^{\lfloor \frac{n}{P} \rfloor}(\lfloor \frac{n}{P} \rfloor)! (\underset{i=1,(i \ mod\ P \neq0)}{\overset{P^k}{\prod}}i)^{\lfloor \frac{n}{P^k} \rfloor}( \underset{i=P^k\lfloor \frac{n}{P^k} \rfloor,(i \ mod\ P \neq0)}{\overset{n}{\prod}}i)
P⌊Pn⌋(⌊Pn⌋)!(i=1,(i mod P=0)∏Pki)⌊Pkn⌋(i=Pk⌊Pkn⌋,(i mod P=0)∏ni)
这里取
P
k
P^k
Pk是因为
P
k
P^k
Pk是这里的模数。
我们要求的是
n
!
P
x
\frac{n!}{P^x}
Pxn!，注意这里的
(
⌊
n
P
⌋
)
!
(\lfloor \frac{n}{P} \rfloor)!
(⌊Pn⌋)!也可能有
P
P
P，故定义函数：
f
(
n
)
=
n
!
P
x
f(n)=\frac{n!}{P^x}
f(n)=Pxn!
故有：
f
(
n
)
=
f
(
⌊
n
P
)
⌋
(
∏
P
k
i
=
1
,
(
i
m
o
d
P
≠
0
)
i
)
⌊
n
P
k
⌋
(
∏
n
i
=
P
k
⌊
n
P
k
⌋
,
(
i
m
o
d
P
≠
0
)
i
)
f(n)=f(\lfloor \frac{n}{P})\rfloor (\underset{i=1,(i \ mod\ P \neq0)}{\overset{P^k}{\prod}}i)^{\lfloor \frac{n}{P^k} \rfloor}( \underset{i=P^k\lfloor \frac{n}{P^k} \rfloor,(i \ mod\ P \neq0)}{\overset{n}{\prod}}i)
f(n)=f(⌊Pn)⌋(i=1,(i mod P=0)∏Pki)⌊Pkn⌋(i=Pk⌊Pkn⌋,(i mod P=0)∏ni)
这样求解
f
(
n
)
f(n)
f(n)的时间复杂度为
O
(
log
P
n
)
O(\log_{P} n)
O(logPn)
考虑下边界即
f
(
0
)
=
0
!
P
0
=
1
f(0)=\frac{0!}{P^0}=1
f(0)=P00!=1
此时我们要求的式子为：
n
!
P
x
m
!
P
y
(
n
−
m
)
!
P
z
P
x
−
y
−
z
m
o
d
P
k
\frac{\frac{n!}{P^x}}{\frac{m!}{P^y}\frac{(n-m)!}{P^z}}P^{x-y-z}\mod P^k
Pym!Pz(n−m)!Pxn!Px−y−zmodPk
=
f
(
n
)
f
(
m
)
f
(
n
−
m
)
P
x
−
y
−
z
m
o
d
P
k
=\frac{f(n)}{f(m)f(n-m)}P^{x-y-z}\mod P^k
=f(m)f(n−m)f(n)Px−y−zmodPk
此时
f
(
m
)
,
f
(
n
−
m
)
f(m),f(n-m)
f(m),f(n−m)都与
P
k
P^k
Pk互质，所以用
e
x
g
c
d
exgcd
exgcd求逆元即可。
那么此时问题还剩
P
x
−
y
−
z
P^{x-y-z}
Px−y−z的求解。
对于该式：
P
⌊
n
P
⌋
(
⌊
n
P
⌋
)
!
(
∏
P
k
i
=
1
,
(
i
m
o
d
P
≠
0
)
i
)
⌊
n
P
k
⌋
(
∏
n
i
=
P
k
⌊
n
P
k
⌋
,
(
i
m
o
d
P
≠
0
)
i
)
P^{\lfloor \frac{n}{P} \rfloor}(\lfloor \frac{n}{P} \rfloor)! (\underset{i=1,(i \ mod\ P \neq0)}{\overset{P^k}{\prod}}i)^{\lfloor \frac{n}{P^k} \rfloor}( \underset{i=P^k\lfloor \frac{n}{P^k} \rfloor,(i \ mod\ P \neq0)}{\overset{n}{\prod}}i)
P⌊Pn⌋(⌊Pn⌋)!(i=1,(i mod P=0)∏Pki)⌊Pkn⌋(i=Pk⌊Pkn⌋,(i mod P=0)∏ni)
幂存在于
P
⌊
n
P
⌋
P^{\lfloor \frac{n}{P} \rfloor}
P⌊Pn⌋和
(
⌊
n
P
⌋
)
!
(\lfloor \frac{n}{P} \rfloor)!
(⌊Pn⌋)!中：
所以设
g
(
n
)
=
⌊
n
P
⌋
+
g
(
⌊
n
P
⌋
)
g(n)=\lfloor \frac{n}{P} \rfloor+g(\lfloor \frac{n}{P} \rfloor)
g(n)=⌊Pn⌋+g(⌊Pn⌋)
时间复杂度仍为
O
(
log
P
n
)
O(\log_{P}n)
O(logPn)
考虑下边界为
g
(
0
)
=
0
g(0)=0
g(0)=0
最终式为：
n
!
P
x
m
!
P
y
(
n
−
m
)
!
P
z
P
g
(
n
)
−
g
(
m
)
−
g
(
n
−
m
)
m
o
d
P
k
\frac{\frac{n!}{P^x}}{\frac{m!}{P^y}\frac{(n-m)!}{P^z}}P^{g(n)-g(m)-g(n-m)}\mod P^k
Pym!Pz(n−m)!Pxn!Pg(n)−g(m)−g(n−m)modPk
最后再用中国剩余定理合并即可。
