组合数取模：阶乘、卢卡斯，以及……等等，模数怎么是合数？！
FallingFYC_
·
·
算法·理论
标题是 ai 起的。
一些定义
阶乘取模
Wilson 定理
对于正整数 n，当且仅当 n 为素数时，成立 (n-1)!\equiv -1~~(\bmod ~n)。
:::info[证明]
通俗一点说就是两个互为逆元的数配对消掉，然后考虑剩下的。
$(\Leftarrow)$ 假设存在合数 $n$ 使得 $(n-1)!\equiv -1\pmod n$，即 $(n-1)!=kn-1$。设 $n=pa$，其中 $p$ 为素数，则 $(n-1)!\equiv -1\pmod p$。但 $(n-1)!$ 含有因子 $p$，故 $(n-1)!\equiv 0\pmod p$，矛盾。因此必要性得证。
:::
#### 推广
Wilson 定理可以推广到对素数幂取模的情形。
对于素数 $p$ 和正整数 $\alpha$，考虑模 $p^\alpha$ 的简化剩余系 $\Phi_{p^\alpha}=\{a \mid 1\le a<p^\alpha \wedge a\perp p\}$，有
$$\prod_{a\in \Phi_{p^\alpha}}a\equiv
\begin{cases}
1&p=2 \wedge \alpha \ge 3\\
-1&\mathrm{otherwise}
\end{cases}
~~~~(\bmod ~p^\alpha)
$$
:::info[证明]
与上面类似的，只用考虑逆元是它本身，即满足方程 $x^2\equiv 1 ~~(\bmod ~p^\alpha)$ 的元素的乘积即可。下面进行分讨。
- 如果 $p$ 为奇质数，方程 $x^2\equiv 1~~(\bmod~~p^\alpha)$ 只有 $x\equiv 1$ 和 $x\equiv -1$ 两个解。因为原方程等价于 $(x+1)(x-1)\equiv 0~~(\bmod ~~p^\alpha)$，而此时 $p^\alpha$ 必定只能整除其中一个。两者的乘积为 $-1$。
- 如果 $p$ 为偶质数，即 $p=2$。我们继续分讨。
- 如果 $\alpha=1$，则原方程只有一个解 $x\equiv -1$。
- 如果 $\alpha=2$，则原方程有两个解 $x\equiv 1$ 和 $x\equiv -1$，乘积为 $-1$。
- 否则，$\alpha\ge 3$，将原方程化为 $(x+1)(x-1)\equiv 0~~(\bmod ~~p^\alpha)$，显然 $x$ 为奇数，因此 $\gcd(x+1,x-1)=2$，故两者一个整除 $2$，另一个整除 $2^{\alpha-1}$，此时有两种情况。
- $x+1=2^{\alpha-1}u$，其中 $u$ 为奇数。由原式可得 $x=2^{\alpha-1}u-1$，即 $x\equiv 2^{\alpha-1}-1$。
- $x-1=2^{\alpha-1}u$，其中 $u$ 为奇数。同上易得 $x\equiv 2^{\alpha-1}+1$。
加上显然的 $x\equiv 1$ 和 $x\equiv -1$，一共四个解。乘积为
$$\begin{aligned}
1\times -1\times (2^{\alpha-1}-1)\times (2^{\alpha-1}+1)&\equiv 1\times -1\times (2^{2\alpha-2}-1)\\
&\equiv 1-2^{2\alpha-2}\equiv 1~~~~(\bmod ~p^{\alpha})\end{aligned}$$
综上，结论成立。
:::
### 阶乘模素数
我们希望计算 $(n!)_p\bmod p$。
注意到这个是有一定递归关系的，以 $(17!)_5\bmod 5$ 为例：
$$
\begin{aligned}
(17!)_5&=1\times 2\times 3\times 4\times 1\\
&~~~~\times 6\times 7\times 8\times 9\times 2\\
&~~~~\times 11\times 12\times 13\times 14\times 3\\
&~~~~\times 16\times 17\\
&\equiv 1\times 2\times 3\times 4\times 1\\
&~~~~~1\times 2\times 3\times 4\times 2\\
&~~~~~1\times 2\times 3\times 4\times 3\\
&~~~~~1\times 2\\
&=(1\times 2\times 3\times 4)^3\times (3!)_5\times (1\times 2) ~~~~(\bmod~ 5)
\end{aligned}
$$
总结以上计算过程可以得到
$$
\begin{aligned}
(n!)_p&\equiv(n-1)!^{\lfloor n/p\rfloor}\times (\lfloor n/p\rfloor!)_p\times (n\bmod p)!\\
&\equiv (-1)^{\lfloor n/p\rfloor}\times (\lfloor n/p\rfloor!)_p\times (n\bmod p)!~~~~(\bmod ~p)
\end{aligned}
$$
#### 推广
我们也将其推广到对素数幂取模的情形。对于素数 $p$ 和正整数 $\alpha$，有
$$(n!)_p\equiv (\pm1)^{\lfloor n/p^\alpha\rfloor}\Big(\prod_{1\le a\le(n\bmod p^{\alpha})\wedge a\perp p}a\Big)(\lfloor n/p\rfloor!)_p~~~~(\bmod ~p^\alpha)$$
其中 $\pm1$ 的取值取决于 Wilson 定理的推广形式。
:::info[证明]
类似之间的思想，把数字按照每 $p^\alpha$ 分为一组。第一项就是一组内的不考虑 $p$ 的倍数的乘积。第二项就是分组后剩下的乘积。第三项同上。
:::
### 阶乘中素数的幂次
我们希望计算 $\nu_p(n!)$。
### Legendre 公式
$$\nu_p(n!)=\sum_{i=1}^{\infin}\lfloor\frac{n}{p^i}\rfloor=\frac{n-s_p(n)}{p-1}$$
其中 $s_p(n)$ 表示 $n$ 在 $p$ 进制下各个位上的数字之和。
:::info[证明]
显然 $n!$ 中 $p$ 的倍数乘积为 $p\times 2p\times \dots\times \lfloor n/p \rfloor p=p^{\lfloor n/p \rfloor}\times \lfloor n/p \rfloor!$，而 $\lfloor n/p \rfloor!$ 可能还有 $p$ 的倍数，于是
$$\nu_p(n!)=\lfloor n/p \rfloor+ \nu_p(\lfloor n/p \rfloor!)$$
展开就得到第一个等号。
之后，把 $n$ 写作一个 $p$ 进制数，$n=\sum_{i=0}^{\mathbb{\ell}}a_ip^i$。
因此有
$$
\begin{aligned}
\nu_p(n!)&=\sum_{i=1}^{\ell} \lfloor \frac{n}{p^i}\rfloor =\sum_{i=1}^{\ell}\sum_{j=i}^{\ell}a_jp^{j-i}=\sum_{j=1}^{\ell}a_j\sum_{i=1}^{j}p^{j-i}\\
&=\sum_{j=1}^{\ell}a_j\frac{p^j-1}{p-1}=\frac{\sum_{j=1}^{\ell}a_jp^j-\sum_{j=1}^{\ell}a_j}{p-1}=\frac{n-s_p(n)}{p-1}\\
\end{aligned}
$$
其中，第二个等号成立是因为 $n=\sum_{j=0}^{i-1}a_jp^j+\sum_{j=i}^{\ell} a_jp^j$ 前者一定 $<p^i$，向下取整后是 $0$，后者一定是 $p^i$ 的倍数。
:::
### Kummer 定理
$$\nu_p\Big(\binom{n}{m}\Big)=\frac{s_p(m)+s_p(n-m)-s_p(n)}{p-1}$$
即 $p$ 在 $\binom{n}{m}$ 中的幂次为 $p$ 进制下 $n$ 减去 $m$ 的借位次数。
:::info[证明]
$$
\begin{aligned}
\nu_p\Big(\binom{n}{m}\Big)&=\nu_p(n!)-\nu_p(m!)-\nu_p((n-m)!)\\
&=\sum_{i=0}^{\infin}(\lfloor\frac{n}{p^i}\rfloor-\lfloor\frac{m}{p^i}\rfloor-\lfloor\frac{n-m}{p^i}\rfloor)\\
&=\frac{s_p(m)+s_p(n-m)-s_p(n)}{p-1}
\end{aligned}
$$
如果在第 $i$ 位（1-index）向第 $i+1$ 位借了一位，则 $n-m$ 第 $i$ 位之前的数 $\lfloor\frac{n-m}{p^i}\rfloor$ 实际上等于 $n$ 第 $i$ 位之前的数 $\lfloor\frac{n}{p^i}\rfloor$ 减去 $1$ 再减去 $m$ 第 $i$ 位之前的数 $\lfloor\frac{m}{p^i}\rfloor$，即
$$\lfloor\frac{n}{p^i}\rfloor-\lfloor\frac{m}{p^i}\rfloor-\lfloor\frac{n-m}{p^i}\rfloor=1$$
$i=0$ 时显然有 $\lfloor\frac{n}{p^i}\rfloor-\lfloor\frac{m}{p^i}\rfloor-\lfloor\frac{n-m}{p^i}\rfloor=0$，于是这恰好对应了上面第二个等号。
:::
## Lucas 定理
对于素数 $p$，有
$$\binom{n}{m} \equiv \binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\binom{n\bmod p}{m\bmod p} ~~~~(\bmod ~p)$$
:::info[证明]
根据定义，显然有
$$n!=p^{\nu_p(n!)}(n!)_p$$
于是
$$
\begin{aligned}
\binom{n}{m}&=\frac{n!}{m!(n-m)!} = p^{\nu_p(n!)-\nu_p(m!)-\nu_p((n-m)!)} \frac{(n!)_p}{(m!)_p(n-m)!_p}\\
\end{aligned}
$$
之前提到过，$\nu_p(n!)$ 和 $(n!)_p \bmod p$ 都有递推公式
$$
\begin{aligned}
\nu_p(n!)&=\lfloor n/p \rfloor+ \nu_p(\lfloor n/p \rfloor!)\\
(n!)_p&\equiv (-1)^{\lfloor n/p\rfloor}\times (\lfloor n/p\rfloor!)_p\times (n\bmod p)!~~~~(\bmod ~p)
\end{aligned}
$$
将他们带入得到
$$
\begin{aligned}
\binom{n}{m}&\equiv p^{\lfloor n/p\rfloor-\lfloor m/p\rfloor-\lfloor (n-m)/p\rfloor} \times p^{\nu_p(\lfloor n/p \rfloor!)-\nu_p(\lfloor m/p \rfloor!)-\nu_p(\lfloor (n-m)/p \rfloor!)}\\
&~~~ \times (-1)^{\lfloor n/p\rfloor-\lfloor m/p\rfloor-\lfloor (n-m)/p\rfloor} \times \frac{(\lfloor n/p\rfloor!)_p}{(\lfloor m/p\rfloor!)_p(\lfloor (n-m)/p\rfloor!)_p} \times \frac{(n\bmod p)!}{(m\bmod p)!((n-m)\bmod p)!}\\
&=(-p)^{\lfloor n/p\rfloor-\lfloor m/p\rfloor-\lfloor (n-m)/p\rfloor} \\
&~~~ \times \frac{(n\bmod p)!}{(m\bmod p)!((n-m)\bmod p)!} \\
&~~~ \times \Big(p^{\nu_p(\lfloor n/p \rfloor!)-\nu_p(\lfloor m/p \rfloor!)-\nu_p(\lfloor (n-m)/p \rfloor!)}\frac{(\lfloor n/p\rfloor!)_p}{(\lfloor m/p\rfloor!)_p(\lfloor (n-m)/p\rfloor!)_p}\Big) ~~~~(\bmod ~p)
\end{aligned}
$$
上面只是带入而已，不要慌。
此时，不能简单地把第二部分写为 $\binom{n\bmod p}{m\bmod p}$，第三部分写为 $\binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}$。因为 $(n-m)\bmod p$ 不一定等于 $n\bmod p-m\bmod p$，$\lfloor (n-m)/p\rfloor$ 不一定等于 $\lfloor n/p\rfloor-\lfloor m/p\rfloor$。
因为有 $n=\lfloor n/p\rfloor p+n\bmod p$，因此
$$
\begin{aligned}
n-m=\lfloor n/p\rfloor p-\lfloor m/p\rfloor p+n\bmod p-m\bmod p &= \lfloor (n-m)/p\rfloor p+(n-m)\bmod p\\
(\lfloor n/p\rfloor-\lfloor m/p\rfloor-\lfloor (n-m)/p\rfloor)p&=(n-m)\bmod p+m\bmod p-n\bmod p\\
\end{aligned}
$$
等式右边小于 $2p$ 因此 $\lfloor n/p\rfloor-\lfloor m/p\rfloor-\lfloor (n-m)/p\rfloor$ 只能等于 $0$ 或 $1$。
- 如果它等于 $0$，则 $(n-m)\bmod p=n\bmod p-m\bmod p$ 且 $\lfloor (n-m)/p\rfloor=\lfloor n/p\rfloor-\lfloor m/p\rfloor$。于是第一个因子系数为 $0$，值为 $1$；后两个因子分别为 $\binom{n\bmod p}{m\bmod p}$ 和 $\binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}$。Lucas 定理成立。
- 如果它等于 $1$，则第一个因子为 $-p$，于是整体就是 $0$。并且有
$$\begin{aligned}
p=(n-m)\bmod p+m\bmod p-n\bmod p\\
p-(n-m)\bmod p=m\bmod p-n\bmod p
\end{aligned}$$
等式左边大于 $0$，于是 $m\bmod p>n\bmod p$。在 Lucas 定理中，$\binom{n\bmod p}{m\bmod p}=0$，整体就是 $0$ 了。
:::
将 $\binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}$ 继续运用此公式展开就得到：
$$
\binom{n}{m} \equiv \prod_{i=0}^{\ell}\binom{n_i}{m_i} ~~~~ (\bmod ~p)
$$
其中 $n=\sum_{i=0}^{\ell} n_ip^i,m=\sum_{i=0}^{\ell} m_ip^i$，即把 $n,m$ 看作 $p$ 进制数。
根据 Lucas 定理，计算组合数对 $p$ 取模求可以拆解成若干 $n,m<p$ 的组合数的乘积。因此可以做到 $O(p)$ 预处理逆元，$O(\log_p n)$ 计算。
:::success[代码]
```cpp
ll fac[N],finv[N],p;
ll qpow(ll a,ll b){
ll res=1;
for(;b;b>>=1ll,a=a*a%p)
if(b&1) res=res*a%p;
return res;
}
ll inv(ll x){return qpow(x,p-2);}
ll C(ll n,ll m){return (n<m?0:fac[n]*finv[m]%p*finv[n-m]%p);}
ll lucas(ll n,ll m){return (m==0?1:C(n%p,m%p)*lucas(n/p,m/p)%p);}
int main(){
CLOSE_TIE
cin>>T;
while(T--){
cin>>n>>m>>p;
fac[0]=finv[0]=1; FOR(i,1,p-1) fac[i]=fac[i-1]*i%p,finv[i]=inv(fac[i]);
cout<<lucas(n+m,n)<<endl;
}
return 0;
}
```
:::
### exLucas
exLucas 解决模数不是素数的情形。
先考虑模数为 $p^\alpha$，其中 $p$ 为素数的情形。考虑类似 Lucas 定理的证明地，将阶乘中 $p$ 和其他因数分开，得到
$$
\binom{n}{m}= p^{\nu_p(n!)-\nu_p(m!)-\nu_p((n-m)!)} \frac{(n!)_p}{(m!)_p(n-m)!_p}
$$
其中 $\nu_p(n!)$ 等使用 Legendre 公式计算，$(n!)_p$ 等使用阶乘对素数幂取模的公式计算。第二项与 $p^\alpha$ 互素，因此用 exgcd 计算逆元即可。
然后对于一般模数就进行素因数分解后列出多个形如上面的方程，用 CRT 解即可。
:::success[代码]
```cpp
ll m,n,p,fac[1000005],ans;
ll nu(ll n,ll p){
ll res=n;
while(n) res-=n%p,n/=p;
res/=p-1;
return res;
}
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b) return x=1,y=0,void();
exgcd(b,a%b,y,x); y-=a/b*x;
}
ll facmod(ll n,ll p,ll alp,ll pw){
if(!n) return 1;
ll n1=(p==2&&alp>=3?1:pw-1);
if(n1==pw-1&&!((n/pw)&1)) n1=1;
return n1*fac[n%pw]%pw*facmod(n/p,p,alp,pw)%pw;
}
ll inv(ll x,ll p){
ll res,tmp; exgcd(x,p,res,tmp);
return (res%p+p)%p;
}
void exLucas(int x,int alp,int mod){
fac[0]=1; FOR(j,1,mod) fac[j]=fac[j-1]*(j%x==0?1:j)%mod;
ll pw=nu(n,x)-nu(m,x)-nu(n-m,x),pwp=1;
if(pw>=alp) return;
FOR(i,1,pw) pwp=pwp*x%mod;
ll v1=facmod(n,x,alp,mod), v2=facmod(m,x,alp,mod), v3=facmod(n-m,x,alp,mod);
ll frac=v1*inv(v2,mod)%mod*inv(v3,mod)%mod;
ll A=pwp*frac%mod;
ll q=p/mod;
ans=(ans+A*q%p*inv(q,mod)%p)%p;
}
int main(){
CLOSE_TIE
cin>>n>>m>>p;
int tp=p;
for(int x=2;x*x<=tp;x++){
if(tp%x==0){
int alp=0,mod=1;
while(tp%x==0) ++alp,tp/=x,mod*=x;
exLucas(x,alp,mod);
}
}
if(tp>1) exLucas(tp,1,tp);
cout<<ans<<endl;
return 0;
}
```
:::
## 例题！
### [P4345 超能粒子炮·改](https://www.luogu.com.cn/problem/P4345)
设 $p=2333$，答案为
$$
\begin{aligned}
f(n,k)&=\sum_{i=0}^k\binom{n}{i} \bmod p\\
&=\sum_{i=0}^k \binom{n/p}{i/p}\binom{n\bmod p}{i\bmod p} \bmod p\\
\end{aligned}
$$
不难发现下面的 $i/p$ 是一个类似于整除分块的形式，于是有
$$
\begin{aligned}
f(n,k)&=\sum_{i=0}^{k/p-1} \binom{n/p}{i} \times \sum_{i=0}^{p-1} \binom{n\bmod p}{i} + \binom{n/p}{k/p}\times \sum_{i=0}^{k\bmod p}\binom{n\bmod p}{i}\\
&=f(n/p,k/p-1)f(n\bmod p,p-1)+\binom{n/p}{k/p}f(n\bmod p,k\bmod p)
\end{aligned}
$$
于是就可以递归处理了。可以预处理 $n,k<p$ 的 $f(n,k)$ 值剪枝。中间组合数那项用 Lucas 定理求。
### [P5598 混乱度](https://www.luogu.com.cn/problem/P5598)
前置知识：多重组合数。也就是题目中的混乱度。我们设可重集 $S$ 的大小为 $n$，且其中有 $a_i$ 个 $i$，则此多重集的排列数为
$$
\binom{n}{a_1,a_2,\dots,a_k}=\frac{n!}{\prod_{i=1}^k (a_i!)}
$$
组合意义就是假设可以区分同色球，则共 $n!$ 种排列。然后对于每种颜色 $i$ 的球，因为实际上无法区分就把相同元素的排列数除掉，即答案除掉 $a_i!$ 。
**它有递推公式（$\binom{n}{a_k}$ 表示的是组合数）**
$$
\binom{n}{a_1,a_2,\dots,a_k}=\binom{n-a_k}{a_1,a_2,\dots,a_{k-1}}\binom{n}{a_k}
$$
我们考虑枚举左端点 $l$，根据多重组合数的递推公式，只要出现 $\binom{n}{a_k}\equiv 0 ~~(\bmod ~p)$，之后的多重组合数的值就都是 $0$ 了，结束枚举。
需要优化。注意到根据 Lucas 定理，我们将 $n,m$ 拆分成 $p$ 进制数 $\overline{n_{\ell}n_{\ell-1}\dots n_0},\overline{m_{\ell}m_{\ell-1}\dotsm_0}$，则有
$$
\binom{n}{m} \equiv \prod_{i=0}^{\ell} \binom{n_i}{m_i} ~~~~(\bmod ~p)
$$
进一步地，有：**如果 $\binom{n+m}{m}\equiv 0 ~~(\bmod ~p)$，则 $n$ 与 $m$ 在 $p$ 进制下相加时产生进位**。这很好理解，毕竟出现上面的情况就是存在一个 $i$ 使得 $n+m$ 的第 $i$ 位小于 $m$ 的第 $i$ 位。越加越小只能是进位了。
我们枚举右端点时，每次加入 $a_r$ 的贡献就是在计算组合数 $\binom{x+a_r}{a_r}$（$x$ 是之前 $a_i$ 的和）。因此我们只需要考虑每次加入 $a_r$ 的贡献时 $x$ 有没有产生进位即可。进一步地，因为 $a_r$ 在 $p$ 进制下为 $0$ 时是没有贡献的，因此每次只考虑非 $0$ 位即可。会发现因为每一位每次都会至少被加上 $1$，因此至多加 $O(p\log_p V)$ 次后就退出了。故而总时间复杂度为 $O(np\log_p V)$。
### [P10594 BZOJ2445 最大团](https://www.luogu.com.cn/problem/P10594)
设 $n$ 个点的 symmetric labeled cliquer（下简称 slc）共 $f(n)$ 个，则答案为
$$m^{f(n)} \bmod(10^9-401)$$
$10^9-401$ 是质数，运用 Fermat 小定理可知答案为 $m^{f(n)\bmod (10^9-402)}\bmod(10^9-401)$。考虑计算指数。一个 slc 的极大连通子图点数一定是 $n$ 的因数。故考虑枚举 $d \mid n$，计算极大连通子图点数为 $d$ 时的图个数。设 $a=n/d$。构造图的过程可以理解为每次从 $n$ 个点选 $d$ 个构成完全图，但这个过程是有序的，所以要除掉 $a!$，即此时答案为
$$\frac{1}{a!}\binom{n}{d,d,\dots,d}=\frac{n!}{(d!)^aa!}$$
$10^9-402=2\times13\times5281\times7283$，是 square-free 的，故考虑计算答案对每个小质数 $p$ 取模的结果再用 CRT 合并。这个问题就可以套用 exLucas 对这类式子的处理方式：把答案中 $p$ 的质因子提出来计算。
### 参考资料
- [阶乘取模——OI Wiki](https://oi-wiki.org/math/number-theory/factorial/)