Lucas定理及组合数取模

蔚落 2022-09-25 03:22 347阅读 0赞

首先给出这个Lucas定理：

A、B是非负整数，p是质数。AB写成p进制：A=a\[n\]a\[n-1\]...a\[0\]，B=b\[n\]b\[n-1\]...b\[0\]。  
则组合数C(A,B)与C(a\[n\],b\[n\])\*C(a\[n-1\],b\[n-1\])\*...\*C(a\[0\],b\[0\])  modp同余

即：Lucas(n,m,p)=c(n%p,m%p)\*Lucas(n/p,m/p,p)

这个定理的证明不是很简单，我一直想找个很好的张明，但是，没找到，昨天看到了一个解题报告，基本上可以说明白这个Lucas定理是怎么回事了，具体的是说：

以求解n! % p为例，把n分段，每p个一段，每一段求的结果是一样的。但是需要单独处理每一段的末尾p, 2p, ...，把p提取出来，会发现剩下的数正好又是(n / p)!，相当于划归成了一个子问题，这样递归求解即可。

这个是单独处理n!的情况，当然C(n,m)就是n!/(m!\*(n-m)!)，每一个阶乘都用上面的方法处理的话，就是Lucas定理了，注意这儿的p是素数是有必要的。

贴一个例题的代码，方便以后看。

[hdu 3037][]

将不大于m颗种子存放在n颗树中，问有多少种存法。

首先是不大于m颗种子，我没可以认为少于m的那些种子存放在了第n+1颗树上，这样的话，问题就转化成了将m颗种子存放在n+1颗树上的方案数。ok这个是组合数学里面的公式，亦即插板法，也就是X1+X2+X3+……+Xn+1 = m;ok，答案是C(n+m,m);

然后就是上面说的Lucas定理解决大组合数问题了

#include <iostream>
    #include <string.h>
    #include <stdio.h>
    using namespace std;
    
    #define N 100010
    
    long long mod_pow(int a,int n,int p)
    {
        long long ret=1;
        long long A=a;
        while(n)
        {
            if (n & 1)
                ret=(ret*A)%p;
            A=(A*A)%p;
            n>>=1;
        }
        return ret;
    }
    
    long long factorial[N];
    
    void init(long long p)
    {
        factorial[0] = 1;
        for(int i = 1;i <= p;i++)
            factorial[i] = factorial[i-1]*i%p;
        //for(int i = 0;i < p;i++)
            //ni[i] = mod_pow(factorial[i],p-2,p);
    }
    
    long long Lucas(long long a,long long k,long long p) //求C(n,m)%p p最大为10^5。a,b可以很大！
    {
        long long re = 1;
        while(a && k)
        {
            long long aa = a%p;long long bb = k%p;
            if(aa < bb) return 0; //这个是最后的改动！
            re = re*factorial[aa]*mod_pow(factorial[bb]*factorial[aa-bb]%p,p-2,p)%p;//这儿的求逆不可先处理
            a /= p;
            k /= p;
        }
        return re;
    }
    
    int main()
    {
        int t;
        cin >> t;
        while(t--)
        {
            long long n,m,p;
            cin >> n >> m >> p;
            init(p);
            cout << Lucas(n+m,m,p) << "\n";
        }
        return 0;
    }

//以上为前几届学长的lucas相关总结，在此基础上，做了少许的修改。

[hdu 3037]: http://acm.hdu.edu.cn/showproblem.php?pid=3037