bzoj3738 [Ontak2013]Kapitał

bzoj3738 [Ontak2013]Kapitał

​​ Description

给出三个数字N,M,K。求C(N+M,N)去掉所有末尾的0后对10^K取模的结果.

1<=N,M<=10^15,1<=k<=9

Input

Output

Sample Input

11 5 9 Sample Output

000004368 HINT

Source

T飞 需要预处理

因为要把10都去掉 所以针对2,5分别讨论下怎么样把多余的可能构成10的那部分去掉即可

就比较一下2,5的个数谁多 如果之前有乘起来就/逆元即可

然后直接用CRT合并一下即可

#include#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline ll read(){ ll x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}inline int ksm(ll b,ll t,int md){static ll tmp; for (tmp=1;t;b=b*b%md,t>>=1) if (t&1) tmp=tmp*b%md;return tmp;}int tot,k,invy[10];ll w[3],c[3],prime[3],mo[3],n,m,fac[2000000];inline void exgcd(ll a,ll b,ll &x,ll &y){ if (!b) {x=1;y=0;return;}exgcd(b,a%b,x,y); ll t=x;x=y;y=t-a/b*y;}inline ll inv(ll a,ll b){ static ll t1,t2;exgcd(a,b,t1,t2);t1=(t1%b+b)%b;return t1;}inline void find_fac(int x){int md=x; for (int i=2;i*i<=md;++i){ if(x%i) continue;prime[++tot]=i;mo[tot]=1; while(x%i==0) mo[tot]*=i,x/=i; }if (x>1) prime[++tot]=x,mo[tot]=x;}inline int get(ll n,int p,int md){ if (!n) return 1;int l=n%md;ll t=1; t=ksm(fac[md],n/md,md);t=t*fac[l]%md; t=t*get(n/p,p,md)%md;return t;}inline ll calc(int p,int md){ static ll t1,t2;ll nm[6];memset(nm,0,sizeof(nm)); fac[0]=1;for (int i=1;i<=md;++i) if (i%p) fac[i]=fac[i-1]*i%md;else fac[i]=fac[i-1]; t1=get(n,p,md);t2=1; for (ll i=2;i<=n;i=i<<1) nm[2]+=n/i; for (ll i=5;i<=n;i=i*5) nm[5]+=n/i; for (int i=1;i<=2;++i) { t2=t2*get(w[i],p,md)%md; for (ll j=2;j<=w[i];j=j<<1) nm[2]-=w[i]/j; for (ll j=5;j<=w[i];j=j*5) nm[5]-=w[i]/j; }t1=t1*inv(t2,md)%md; if (p==2) { if (nm[2]>nm[5]) t1=t1*ksm(invy[p],nm[5],md)%md,t1=t1*ksm(p,nm[2]-nm[5],md)%md; if (nm[2]nm[2]) t1=t1*ksm(invy[p],nm[2],md)%md,t1=t1*ksm(p,nm[5]-nm[2],md)%md; if (nm[5]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。