卢卡斯(Lucas)定理

对此C(n, m) mod p。这里的n,m,p(p为素数)都很大的气象。就无法再用C(n,
m) = C(n – 1,m) + C(n – 1, m – 1)的公式递推了。

用lucas定理, p必须是素数

有武圣式
C(n,m)=n!/m!(n-m)!
 中蕴含除法,我们得以不能够一向将n!和m!和(n-m)!直接取模再相除

于是乎就拿到了卢卡斯(Lucas)定理:C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p

 对于单身的C(n, m) mod p,已知C(n, m) mod p = n!/(m!(n – m)!) mod
p。显明除法取模,这里要用到m!(n-m)!的逆元。

因而这边需要求逆元,我们先预处理出每一个阶乘的逆元,然后再代入公式得:

根据费马小定理

据悉费马小定理:

C(n,m)=n!*ni(m)*ni(n-m)
%mod   ni[i]为i的逆元

已知(a, p) = 1,则 ap-1 ≡ 1 (mod p),  所以
a*ap-2 ≡ 1 (mod p)。

已知(a, p) = 1,则 ap-1 ≡ 1 (mod p),  所以
a*ap-2 ≡ 1 (mod p)。

 

也就是 (m!(n-m)!)的逆元为 (m!(n-m)!)p-2\ ;

也就是 (m!(n-m)!)的逆元为 (m!(n-m)!)p-2\ ;

求逆元可以用费马小定理,也足以用扩张欧几里得,增加欧几里得可以参考这篇博客,费马小定理在该博客将提交结论

从而就用很快幂就可以缓解了,也可以用扩大欧几里得算法,也可以了。

所以C(n, m) mod p = n! * (m! * (n – m)! )^(p-2)%mod

费马小定理:

typedef long long LL;
using namespace std;

LL exp_mod(LL a, LL b, LL p) {
    LL res = 1;
    while(b != 0) {
        if(b&1) res = (res * a) % p;
        a = (a*a) % p;
        b >>= 1;
    }
    return res;
}

LL Comb(LL a, LL b, LL p) {
    if(a < b)   return 0;
    if(a == b)  return 1;
    if(b > a - b)   b = a - b;

    LL ans = 1, ca = 1, cb = 1;
    for(LL i = 0; i < b; ++i) {
        ca = (ca * (a - i))%p;
        cb = (cb * (b - i))%p;
    }
    ans = (ca*exp_mod(cb, p - 2, p)) % p;
    return ans;
}

LL Lucas(int n, int m, int p) {
     LL ans = 1;

     while(n&&m&&ans) {
        ans = (ans*Comb(n%p, m%p, p)) % p;
        n /= p;
        m /= p;
     }
     return ans;
}

int main() {
    Read();
    int n, m, p;
    while(~scanf("%d%d%d", &n, &m, &p)) {
        printf("%lld\n", Lucas(n, m, p));
    }
    return 0;
}

高中级用高速幂取余

只要p是质数,且gcd(a,p)=1,那么
a(p-1)≡1(mod
p),即:假设a是整数,p是质数,且a,p互质(即双方唯有一个公约数1),那么a的(p-1)次方除以p的余数恒等于1。

这是一个费马小定理的代码

图片 1图片 2

显然 ni(a)=a^(p-2)

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cassert>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-7;
const int N=1000000+10,maxn=300000+10,inf=0x3f3f3f;

ll fac[N],a,b;
bool ok(ll x)
{
    while(x){
        if(x%10!=a&&x%10!=b)return 0;
        x/=10;
    }
    return 1;
}
ll quick(ll a,ll b)
{
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    fac[0]=fac[1]=1;
    for(ll i=2;i<N;i++)
        fac[i]=fac[i-1]*i%mod;
    ll n,ans=0;
    cin>>a>>b>>n;
    for(ll i=0;i<=n;i++)
        if(ok(a*i+(n-i)*b))
            ans=(ans+fac[n]*quick(fac[i]*fac[n-i]%mod,mod-2)%mod)%mod;
    cout<<ans<<endl;
    return 0;
}
/********************

********************/

 

View Code

 1 ll qm(ll x,ll k){   //快速幂
 2     if(k==0)return 1;
 3     ll sum=1;
 4     while(k){
 5         if(k&1)sum*=x,sum%=mod;
 6         k>>=1;x*=x;
 7         x%=mod;
 8     }
 9     return sum;
10 }
11 ll ni[N],f[N]; //fi为i的阶乘
12 void prework(){
13     f[0]=1;ni[0]=qm(f[0],mod-2);
14     for(int i=1;i<=n;i++){
15         f[i]=f[i-1]*i;f[i]%=mod;
16         ni[i]=qm(f[i],mod-2);
17     }
18 }

 

 

 

预处理出逆元那么就可以用上述公式O(1)求得组合数C(n,m)了

 

1 ll query(int n,int m){
2     ll ret=((f[n]*ni[m]%mod)*(ni[n-m]))%mod;
3     return ret;
4 }

 

相关文章