hdu3037 Lucas定理

Lucas定理

　　Lucas(n,m,p)=c(n%p,m%p)* Lucas(n/p,m/p,p)，其中lucas(n,m,p)=C(n,m)%p

　　(这里的除号是整除)

证明——百度百科

题意：求n个数的和<=m的方案数

题解：

　　求a1+a2+ ... +an=m方案数, 利用隔板法要使得每个数>=1，所以令bi = ai+1>=1 则 b1+b2+ ... +bn=m+n方案数为C(m+n-1, n-1)=C(m+n-1, m)

　　故 ans = sigama(C(i+n-1, i)) = C(n-1, 0) + C(n, 1) + C(n+1, 2) + ... + C(n+m-1, m) = C(n+m, m)

　　剩下的就是Lucas定理的应用了。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <cmath>

#include <utility>

#include <vector>

#include <queue>

#include <map>

#include <set>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)>(y)?(y):(x))

#define INF 0x3f3f3f3f

using namespace std;

long long fac[];

long long quick(long long a, long long n, long long p)

{

    long long tmp=a%p, ret=;

    while(n)

    {

        if(n&)

            ret=(ret*tmp)%p;

        tmp=(tmp*tmp)%p;

        n>>=;

    }

    return ret%p;

}

long long C(long long n, long long m, long long p)

{

    if(m>n) return ;

    fac[]=;

    for(int i=; i<=n; i++)

        fac[i]=(fac[i-]*i)%p;

    return (fac[n]*quick(fac[m]*fac[n-m], p-, p))%p;

}

long long Lucas(long long n, long long m, long long p)

{

    long long ret=;

    while(n && m)

    {

        ret=ret*C(n%p, m%p, p)%p;//注意 C(10, 8) % 9这类情况

        n/=p;

        m/=p;

    }

    return ret;

}

long long n,m,p;

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        scanf("%I64d%I64d%I64d", &n, &m, &p);

        printf("%I64d\n", Lucas(n+m, m, p));

    }

    return ;

}