1 条题解

  • 1
    @ 2017-10-31 17:02:19
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll n, m, p;
    ll powd(ll a, ll k)// 快速幂 
    {
        ll ans=1;
        while(k) 
        {
            if(k&1)ans=(ans*a)%p;
            a=(a*a)%p;
            k>>=1;
        }
        return ans;
    }
    ll C(ll a,ll b,ll p)// 组合数 
    {
        if(a<b)
            return 0;
        if(b>a-b)
            b=a-b;
        ll up=1,down=1;
        for (ll i=0;i<b;i++) 
        {
            up=up*(a-i)%p;
            down=down*(i+1)%p;
        }
        return up*powd(down,p-2)%p; // 费马小定理求逆元,不懂一定要去看看 !!!! 
    }
    ll lucas(ll a,ll b,ll p)
    {
        if (b == 0)
            return 1;
        return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
    }
    int main()
    {
        cin>>n>>m>>p;
        cout<<lucas(n,m,p)<<endl;
        return 0;
    }
    
  • 1

信息

难度
8
分类
(无)
标签
(无)
递交数
18
已通过
5
通过率
28%
上传者