问题引入

今天做到了个普普通通的排列组合题，P2606 ZJOI2010 排列计数。

剧透一下做法，构造一个大小为$n$的完全二叉堆，其下标依据标准的堆设定，即$x$的左右儿子下标分别为$2x$和$2x+1$，$tot_{x}$表示根为$x$的子树大小（包括自身）。

令$f(x)$为以$x$为根的答案，设$l$为左儿子，$r$为右儿子则$$f(x)=C_{tot_{x}-1}^{tot_{l}} f(l) f(r)$$ （当$l$ $r$ 不存在的时候对应地替换为$1$） 再应用取模运算的相关方法，其模数$p$保证是一个质数，递归求解$f(1)$即为所求。

正题

问题来了，取模运算实际上是有问题的。

首先模意义下的阶乘，也就是$$fac(x)=fac(x-1)x\ mod\ p$$是符合定义的

问题在于取逆，以质数为模数不是所有整数都存在逆吗？ 答：$0$是没有逆的。

也就是说，如果$p\mid n!$，那么$n!$不存在模$p$意义下的逆。

尽管逆不存在，但任意的$C_{n}^{m}\ mod\ p$却是显然存在的。这个时候就用到了$Lucas$定理，保证对于任意$n,m$，总能求到对应的$C_{n}^{m}\ mod\ p$，表达式如下：$$C_{n}^{m}\ mod\ p=C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor} C_{n\ mod\ p}^{m\ mod\ p}\ mod p$$

特别限定$n>p \lor m>p$时递归求解，否则使用正常的组合数函数。

AC代码

#include <iostream>
using namespace std;
const int maxn = 1e6 + 1;
using ll =long long;
#define int long long
int L[maxn],R[maxn];
int tot[maxn];
int m;
int n;
void dfs(int cur){
    tot[cur]=1;
    if(cur*2<=n){
        L[cur]=cur*2;
        dfs(cur*2);
        tot[cur]+=tot[L[cur]];
    }
    if(cur*2+1<=n){
        R[cur]=cur*2+1;
        dfs(cur*2+1);
        tot[cur]+=tot[R[cur]];
    }
}
int fac[maxn],inv[maxn];
int qpow(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1)
            res=(ll)res*a%p;
        a=(ll)a*a%p;
        k>>=1;
    }
    return res;
}
void mkfac(){
    fac[0]=inv[0]=1;
    for(int i=1;i<maxn;i++){
        fac[i]=(ll)fac[i-1]*i%m;
        inv[i]=(ll)inv[i-1]*qpow(i,m-2,m)%m;
    }
}
int Comb(int a,int b){
    static constexpr auto C = [](int a,int b){
        return fac[a]*inv[a-b]%m*inv[b]%m;
    };
    if(a<m && b<m)
        return C(a,b);
    return (ll)C(a%m,b%m)*Comb(a/m,b/m)%m;
}
int ans=1;
void calc(int cur){
    if(L[cur]){
        ans=ans*Comb(tot[cur]-1,tot[L[cur]])%m;
        calc(L[cur]);
    }
    if(R[cur])
        calc(R[cur]);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    mkfac();
    dfs(1);
    calc(1);
    cout<<ans;
    return 0;
}

拓展阅读

$Lucas$定理的细致讲解，包含了证明过程和适用例：OI Wiki 卢卡斯定理