首页 > 代码库 > BZOJ 4403 2982 Lucas定理模板

BZOJ 4403 2982 Lucas定理模板

思路:

Lucas定理的模板题..

4403

//By SiriusRen#include <cstdio>using namespace std;const int mod=1000003;#define int long longint cases,N,L,R,fac[mod],inv[mod];int C(int n,int m){    if(n<m)return 0;    if(n<mod&&m<mod)return fac[n]*inv[n-m]%mod*inv[m]%mod;    return C(n/mod,m/mod)*C(n%mod,m%mod)%mod;}signed main(){    fac[0]=inv[0]=inv[1]=1;    for(int i=1;i<mod;i++)fac[i]=fac[i-1]*i%mod;    for(int i=2;i<mod;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;    for(int i=1;i<mod;i++)inv[i]=inv[i-1]*inv[i]%mod;    scanf("%lld",&cases);    while(cases--)scanf("%lld%lld%lld",&N,&L,&R),printf("%lld\n",(C(N+R-L+1,R-L+1)-1+mod)%mod);}

 

2982

//By SiriusRen#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define int long longconst int p=10007;int fac[p],inv[p],n,m,cases;int C(int i,int j){    if(i<j)return 0;    if(i<p&&j<p)return fac[i]*inv[j]%p*inv[i-j]%p;    return C(i/p,j/p)*C(i%p,j%p)%p;}signed main(){    fac[0]=fac[1]=inv[0]=inv[1]=1;    for(int i=2;i<p;i++)fac[i]=fac[i-1]*i%p;    for(int i=2;i<p;i++)inv[i]=(p-p/i)*inv[p%i]%p;    for(int i=1;i<p;i++)inv[i]=inv[i-1]*inv[i]%p;    scanf("%lld",&cases);    while(cases--){        scanf("%lld%lld",&n,&m);        printf("%lld\n",C(n,m));    }}

 

BZOJ 4403 2982 Lucas定理模板