数学杂谈#2

一般的 Lucas 定理

~~相信你应该很熟练了~~

Lucas 定理

普通 Lucas 定理的形式如下：

对于正整数 (n,m) 和素数 (p) ，有：

[inom{n}{m}equiv inom{lfloorfrac{n}{p} floor}{lfloorfrac{m}{p} floor}inom{nmod p}{mmod p}pmod p ]

为了方便，下面我们将 (lfloorfrac{n}{p} floor) 直接记作 (n/p) ，所以 Lucas 定理就是：

[inom n m equiv inom{n/p}{m/p}inom{nmod p}{mmod p}pmod p ]

简单证明：

利用如下等式：

[(1+x)^pequiv 1+x^ppmod{p} ]

二项式定理：

[egin{aligned} (1+x)^p &equiv sum_{i=0}^pinom{p}{i}x^ipmod p\ end{aligned} ]
注意到当 (1le k<p) 的时候， (inom{p}{k}) 都必然含有 (p) 因子，所以：

[(1+x)^pequiv 1+x^ppmod p ]

另一个更快的方式是使用费马小定理。设 (y=1+x) ，则：

[y^pequiv yequiv 1+xequiv 1+x^ppmod p ]

设 (n=kp+r(0le r<p)) 。

那么就有：

[egin{aligned} (1+x)^n &equiv (1+x)^{k*p}(1+x)^{r}pmod{p}\ &equiv (1+x^p)^{k}(1+x)^{r}pmod{p}\ &equiv sum_{i=0}^{k}inom{k}{i}x^{ip}sum_{j=0}^{r}inom{r}{j}x^jpmod{p}\ sum_{i=0}^ninom{n}{i}x^i &equiv sum_{i=0}^kinom{k}{i}x^{ip}sum_{j=0}^rinom{r}{j}x^{j}pmod{p}\ end{aligned} ]

两边同时取 ([x^m](0le mle n)) 。设 (m=sp+t(0le t<p)) ，当 (tle r) 的时候，有：

[inom{n}{m}equiv inom{k}{s}inom{r}{t}pmod p ]

注意，当 (t>r) 的时候，必然有 (inom{n}{m}mod p= 0) ，而此时 (inom{r}{t}mod p=0) ，所以可以写作这个形式。

为什么当 (t>r) 时，有 (inom{n}{m}=0) ？

这就意味着， (inom{n}{m}) 包含 (p) 因子。

利用勒让德定理，其中 (p) 的次数为：

[sum_{k=1}n/p^k-m/p^k-(n-m)/p^k ]
显然每一位都 (ge 0) 。

结合 (t>r) ，所以 (m+(n-m)) 在 (p) 进制下的 (p^0) 这一位必然是进了位的，所以有：

[n/p-m/p-(n-m)/p>0 ]
因此 (inom{n}{m}) 必包含 (p) 。

Lucas 定理的运用

Lucas 定理一般拿来计算组合数取模的值。

~~这难道不是它的本职工作吗~~

当 (p) 比较小的时候，我们可以预处理一下 (n,m<p) 时候的组合数，然后就可以递归算。

时间是 (O(p)-O(log_p n)) 。

当 (p) 不是素数的时候，需要使用 exLucas 计算。

关于 Lucas 定理的扩展内容

仔细观察 Lucas 定理。设 (n=(n_1n_2ldots n_k)_p,m=(m_1m_2ldots m_k)_p) ，那么有：

[egin{aligned} inom{n}{m}equivprod_{i=1}^k inom{n_i}{m_i}pmod p end{aligned} ]

因此， Lucas 定理相当于是在 (p) 进制下，对每一位单独算组合数，最后合起来。

这也告诉我们，在 (p) 进制中，每一位的组合数是独立的，我们就可以进行数位 DP 等等。

例题：[清华集训2016] 组合数问题。

计算进位次数。

~~这真的有关系吗？~~

这里需要祭出一个 Kummer 定理：

对于正整数 (n,p) ，设 (old v_p(n)) 为 (n) 所包含的 (p) 的幂次。

对于正整数 (n,m) 和素数 (p) ， (old v_p(inom{n}{m})) 即为 (m+(n-m)) 在 (p) 进制下的进位次数。

~~看起来就像在扯淡~~

简单证明：

计算一下 (old v_p(inom n m)) ：

[sum_{k=1}n/p^k-m/p^k-(n-m)/p^k ]

另外，对于正整数 (n,m,p) ，都有恒等式成立：

[n/p-m/p-(n-m)/p=[mmod p+(n-m)mod pge p] ]

所以有：

[old v_p(inom n m)=sum_{k=1}[mmod p^k+(n-m)mod p^kge p^k] ]

所以就是枚举判断 (p) 进制下的第 (k) 位是否进位。

关于恒等式的证明：

设 (n=v_1p+k_1,m=v_2p+k_2,(n-m)=v_3p+k_3(0le k_1,k_2,k_3<p)) 。

现在考虑 (n/p-m/p-(n-m)/p=v_1-v_2-v_3) ，如果有进位，则 (v_1-v_2-v_3=1) ，否则有 (v_1-v_2-v_3=0) 。

另一方面，如果有进位，那么余数应该加和大于 (p) ，所以如果 (k_2+k_3ge p) ，则有进位，否则没有进位。

一般这个性质可以用在数位 DP 里面。

~~啊这，跟 Lucas 定理有什么关系吗？~~

一个比较有意思的转化。

根据 Lucas 定理，我们知道：

[inom{n}{m}equiv inom{n/p}{m/p}inom {nmod p}{mmod p}pmod p ]

但是，对于形式变元 (x^n) ，也有：

[x^nequiv x^{n/p*p}x^{nmod p}equiv x^{n/p}x^{nmod p}pmod p ]

这个形式和 Lucas 定理很像不是吗？考虑将两者结合起来看：

[inom{n}{m}x^nequiv inom{n/p}{m/p}x^{n/p} imes inom{nmod p}{mmod p}x^{nmod p}pmod p ]

当然，如果将 (x^n) 换做 (x^m) ，效果也是几乎一样的。

在一个实际的例子中，我们可以计算：

[sum_{i=1}^minom{n}{i}x^imod p ]

根据上面的式子推导一下：

[egin{aligned} sum_{i=0}^minom{n}{i}x^i &equiv sum_{i=1}^minom{n/p}{i/p}x^{i/p}inom{nmod p}{imod p}x^{imod p} pmod p\ &equiv left(sum_{t=0}^{m/p-1}inom{n/p}{t}x^t ight)left(sum_{k=0}^{p-1}inom{nmod p}{k}x^k ight)+inom{n/p}{m/p}x^{m/p}sum_{k=0}^{mmod p}inom{nmod p}{k}x^kpmod p\ end{aligned} ]

计算这个式子的时候，由于 (n) 固定，所以 (nmod p) 只有 (O(log_p n)) 种有效取值，对于每种取值都可以预处理出 (inom{nmod p}{k}x^k) 的前缀和，所以可以 (O(plog_p n)) 预处理，再 (O(log_p m)) 计算一次答案。

exLucas

一般认为 exLucas 是一个算法，跟 Lucas 作为定理的本质不同。

exLucas 求解的也是组合数取模的问题。

也就是，对于正整数 (n,m) 和任意较小正整数 (P) ，我们都可以较快地计算 (inom{n}{m}mod P) 的结果。

第一步

我们需要将 (P) 进行分解，拆分成 (prod_{i=1}^kp_i^{e_i}) 。根据 CRT 我们知道 (inom{n}{m}) 对于每个 (p_i^{e_i}) 取模的结果最终必然可以唯一确定一个 (mod P) 意义下的值。

第二步

考虑计算 (inom{n}{m}mod p^e) ，其中 (p) 是素数，且 (e) 是正整数。

将组合数展开成阶乘：

[egin{aligned} inom{n}{m} &equiv frac{n!}{m!(n-m)!}pmod {p^e}\ &equiv frac{frac{n!}{p^{old v_p(n!)}}}{frac{m!}{p^{old v_p(m!)}}frac{(n-m)！}{p^{old v_p((n-m)!)}}} imes p^{old v_p(n!)-old v_p(m!)-old v_p((n-m)!)}pmod {p^e}\ end{aligned} ]

后一步提出 (p) 因子变化是很有必要的，不然我们极有可能会在直接 (n!) 计算的过程中算出三个 0 ，然后只能发呆......

其中 (old v_p(n!)) 三个部分可以使用 Legendre 定理计算。

第三步

设 (f(n)=frac{n!}{p^{old v_p(n!)}}mod p^e) ，我们现在只需要能快速计算 (f) 的值即可。

考虑参考 Lucas 定理的证明过程，将 (n!) 的因子分类：

[egin{aligned} n! &=(Pcdot 2Pcdot 3Pcdotldots)(1cdot 2cdot 3cdotldotscdot kP-1cdot kP+1cdotldots)\ &=left(prod_{1le ile n,imod p eq 0} i ight)left(prod_{1le jle n,jmod p=0}j ight)\ &=p^{n/p}(n/p)! imes left(prod_{1le ile p^e,imod p ot=0}i ight)^{n/p^e}left(prod_{n/p^e imes p^e<jle n,jmod p ot=0}j ight) end{aligned} ]

注意到最终结果的第一个 (prod) 内的值是不随 (n) 变化的，因此可以直接统计它的幂次之和，最后一次计算；而 ((n/p^e imes p^e,n]) 的尾巴部分，在 (mod p^e) 意义下等价于 ((0,nmod p^e]) ，因此可以预处理一组互质前缀积。

计算时间是 (O(p^e)-O(log_pn)) 。

可以发现 exLucas 最有用的部分其实就是 第三步 内提到的阶乘算法。因此 exLucas 也可用于计算 (p^e) 较小时候的阶乘。

~~再大？再大就得写多项式了~~