首页 > 代码库 > 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定理模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。