ZOJ 3557 & BZOJ 2982 combination[Lucas定理]

How Many Sets II

Time Limit: 2 Seconds Memory Limit: 65536 KB

Given a set S = {1, 2, ..., n}, number m and p, your job is to count how many set T satisfies the following condition:

T is a subset of S
|T| = m
T does not contain continuous numbers, that is to say x and x+1 can not both in T

Input

There are multiple cases, each contains 3 integers n ( 1 <= n <= 10⁹ ), m ( 0 <= m <= 10⁴, m <= n ) and p ( p is prime, 1 <= p <= 10⁹ ) in one line seperated by a single space, proceed to the end of file.

Output

Output the total number mod p.

Lucas定理p为质数情况裸题

因为是选的元素不能连续，我们先把选的元素拿出来，剩下的元素有n-m+1个空，选m个插进去行了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

ll n,m,P;

ll Pow(ll a,ll b){

    ll ans=;

    for(;b;b>>=,a=a*a%P)

        if(b&) ans=ans*a%P;

    return ans;

}

ll Inv(ll a){return Pow(a,P-);}

ll C(ll n,ll m){

    if(n<m) return ;

    ll x=,y=;

    for(ll i=n-m+;i<=n;i++) x=x*i%P;

    for(ll i=;i<=m;i++) y=y*i%P;

    return x*Inv(y)%P;

}

ll Lucas(ll n,ll m){

    if(n<m) return ;

    ll re=;

    for(;m;n/=P,m/=P) re=re*C(n%P,m%P)%P;

    return re;

}

int main(){

    //freopen("in","r",stdin);

    while(scanf("%lld%lld%lld",&n,&m,&P)!=EOF)

        printf("%lld\n",Lucas(n-m+,m));

}

BZOJ 2982: combination

模数10007很小，可以直接线性预处理阶乘和逆元，48ms-->4ms

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=;

inline ll read(){

    char c=getchar();ll x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

ll n,m,P=;

ll inv[N],fac[N],facInv[N];

void getInv(int n){

    inv[]=fac[]=facInv[]=;

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

        if(i!=) inv[i]=-P/i*inv[P%i]%P;

           inv[i]+=inv[i]<?P:;

        fac[i]=fac[i-]*i%P;

        facInv[i]=facInv[i-]*inv[i]%P;

    }

}

ll C(ll n,ll m){

    if(n<m) return ;

    return fac[n]*facInv[m]%P*facInv[n-m]%P;

}

ll Lucas(ll n,ll m){

    if(n<m) return ;

    ll re=;

    for(;m;n/=P,m/=P) re=re*C(n%P,m%P)%P;

    return re;

}

int main(){

    freopen("in","r",stdin);

    getInv(N-);

    int T=read();

    while(T--){

        n=read();m=read();

        printf("%lld\n",Lucas(n,m));

    }

}