组合数性质

组合数为奇数的情况

组合数$C(n,k)$为奇数，当且仅当$k$是$n$的子码(submask)（也就是说，$n\&k=k$）

---

证明如下：

$C(n,k)=\frac{n!}{k!(n-k)!}$，因此要判断$C(n,k)$的奇偶性，只需要知道$n!,k!,(n-k)!$的素数分解中$2$个数

设$n!,k!,(n-k)!$中$2$的个数分别为$a,b,c$，显然有$a\ge b+c$，当且仅当$a=b+c$时组合数为奇数

由勒让德定理，可知

$$a=L_2(n!)=\sum\limits_{k\ge 1} \left\lfloor \frac{n}{2^k}\right\rfloor$$

定义函数$g(x)=x$，有

$$\newcommand{\floordiv}[2]{\left\lfloor\frac{#1}{#2}\right\rfloor}\begin{aligned}g(x)&=x\\&=\floordiv{n}{2}+\floordiv{n}{2}+(x\% 2)\\&=\floordiv{n}{2}+g(\floordiv{n}{2})+(x\% 2)\\&=\sum\limits_{i\ge1}\floordiv{x}{2^i}+\sum\limits_{i\ge0}(\floordiv{x}{2^i}\% 2)\\&=L_2(x!)+\sum\limits_{i\ge0}(\floordiv{x}{2^i}\% 2)\end{aligned}$$

令$f(x)=\text{x的二进制表示中，1的个数}$，显然有

$$\newcommand{\floordiv}[2]{\left\lfloor\frac{#1}{#2}\right\rfloor}f(x)=\sum\limits_{i\ge0}(\floordiv{x}{2^i}\% 2)$$

因此，$a=L_2(n!)=n-f(n)$，同理，$b=k-f(k),c=(n-k)-f(n-k)$

当$a=b+c$时，即$f(n)=f(k)+f(n-k)$

由数学归纳法可以证明：$f(n)\le f(k)+f(n-k)$，当且仅当$(k\&n)=k$时等号成立

参考：

• https://blog.csdn.net/netown_ethereal/article/details/35234873
• https://blog.csdn.net/weixin_40859716/article/details/84647291

组合数求法

卢卡斯定理（求余组合数）

$$\begin{pmatrix}sp+q\\tp+r\end{pmatrix}=\begin{pmatrix}s\\t\end{pmatrix}\begin{pmatrix}q\\r\end{pmatrix}\mod p$$

$C(n,m)\% p=C(n/p,m/p)*C(n\%p,m\%p)\%p$ （$n/p,m/p$均为板除）

编写程序时，使用下面这条等式：

$$Lucas(n,m,p)=C(n\%p,m\%p)*Lucas(n/p,m/p,p)\mod p$$

证明

对于质数$p$，对于$1\le i\lt p$有

$$\begin{aligned}C(p,i)&=\frac{p}{i}C(p-1,i-1)\\&\equiv p\times inv(i)\times C(p-1,i-1) \mod p\\&\equiv0\mod p\end{aligned}$$

再由二项式定理定理得$(1+x)^p=1+C(p,1)x+\dots+C(p,p-1)x^{p-1}+x^p\equiv1+x^p\mod p$

---

由二项式定理可知

$$(1+x)^n=\sum\limits_{i=0}\limits^{n}C(n, i)x^i$$

对于求$C(n,m)$，可以转化为求$(1+x)^n$展开式中$x^m$的系数。

令$n=sp+q,m=tp+r$

则

$$\begin{aligned}(1+x)^n&=(1+x)^{sp}\cdot(1+x)^q\\&\equiv (1+x^p)^s\cdot(1+x)^q \mod p\end{aligned}$$

因此

$$\begin{aligned}C(n,m)x^m & \equiv C(s,t)(x^p)^t\cdot C(q,r)x^r\mod p \\& \equiv C(s,t)\cdot C(q,r)\cdot x^m\mod p\\\therefore C(n,m) & \equiv C(\lfloor \frac{n}{p}\rfloor,\lfloor \frac{m}{p} \rfloor ) \cdot C(n\%p,m\%p) \mod p\end{aligned}$$

例题 洛谷P3807

题意：给定$a,b,p$，求$C(a+b,b)\mod p\quad (p\le10^5)$

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll mod;
ll inv(ll base){
    ll ret = 1, t = mod - 2;
    for(;t; t>>=1){
        if(t & 1) ret = ret * base % mod;
        base = base * base % mod;
    }
    return ret;
}
// 暴力求组合数，有优化空间
ll Comb(ll n, ll m){
    if(n < m) return 0;
    if(n - m < m) m = n - m;
    ll denom = 1, numer = 1;
    for(int i=0; i<m; i++){
        numer = numer * (n - i) % mod;
        denom = denom * (i + 1) % mod;
    }
    return numer * inv(denom) % mod;
}

ll Lucas(ll n, ll m){
    if(m == 0) return 1;
    return Lucas(n / mod, m / mod) * Comb(n % mod, m % mod) % mod;
}

signed main(){
    int t; cin >> t;
    while(t--) {
        ll a, b;
        cin >> a >> b >> mod;
        cout << Lucas(a + b, a) << '\n';
    }
}