p3807(lucas定理)

题目链接:https://www.luogu.org/problemnew/show/P3807

 

题意:求C(n,n+m)%p

思路:这是Lucas模板题,下面就介绍下lucas定理:

lucas定理(大组合数取模)结论:
      C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p

证明:

前提定理:1.设1<=j<=p-1,都有C(j,p)≡0(mod p)

证明:C(j,p)=p!/(j!*(p-j)!)=(p/j)*  (p-1)!/((j-1)!*((p-1)-(j-1))!=(p/j)*C(j-1,p-1)≡0(mod p)

    2.(1+x)p=1+C(1,p)x+C(2,p)x2+...+C(p-1,p)xp-1+xp≡1+xp(mod p)(根据定理1得)
  因为m=(m/p)*p+m%p;(m/p是商,m%p是余数)

      (1+x)m=(1+x)m/p*p * (1+x)m%p≡(1+xp)m/p*(1+x)m%p
两边系数要同余
所以两边xn系数:
C(n,m)≡C(n/p,m/p)*(n%p,m%p)(mod p)

 

代码求解过程中,不断将C(n/p,m/p)拆分化简,实质是一直在计算C(n%p,m%p),即:
C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p
等价于C(n,m)%p=C(n/p/p,m/p/p)*C(n/p%p,m/p%p)%p
等价于C(n,m)%p=C(n/p/p/p,m/p/p/p)*C(n/p/p%p,m/p/p%p)%p
等价于…
直到拆分至m=0,递归完成。

代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;

ll q_pow(ll a,ll b,ll p)//快速幂用来求逆元 
{
    ll ans=1;
    while(b) 
    {
        if(b&1)
            ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}

ll comb(ll a,ll b,ll p)//求组合数 
{
    if(a<b)    return 0;
    if(b==a) return 1;
    if(b>a-b) b=a-b;
    ll ans=1,ca=1,cb=1;
    for(int i=0; i<b; i++) 
    {
        ca=(ca*(a-i))%p;
        cb=(cb*(b-i))%p;
    }
    ans=(ca*q_pow(cb,p-2,p))%p;
    return ans;
}

ll lucas(ll a,ll b,ll p)//lucas 
{
    ll ans=1;
    while(a&&b&&ans) 
    {
        ans=(ans*comb(a%p,b%p,p))%p;
        a/=p;
        b/=p;
    }
    return ans%p;
}

int main() 
{
    ll t,n,m,p;
    cin>>t;
    while(t--) 
    {
        cin>>n>>m>>p;
        cout<<lucas(n+m,n,p)<<endl;
    }
    return 0;
}

 

上一篇:微软公布针对最新IE漏洞的安全通报2963983


下一篇:雷林鹏分享:jQuery EasyUI 布局 - 创建 XP 风格左侧面板