CodeVS2505 上学路线

2019-11-06 08:47:00

字体：大中小

来源：转载

供稿：网友

链接

　　http://codevs.cn/PRoblem/2505/

题解

　　根据结论，我们要求的是Cn−1n+m−2 $C_{n+m-2}^{n-1}$ 　　这很容易….但，这道题是高精度！　　这让人很不爽，首先想到的是直接套用组合数公式然后高精度乘法+高精度除法。什么？高精除？貌似想切下一题了…. 　　不慌，易知组合数一定是整数，所以我们可以约分。但是极端数据20000*20000，如果分子分母约分的话是O(n2) $O(n^2)$ 的，会T。　　于是我们分解质因数，那就要先筛素数。　　把分子分解质因数之后，拿分母分解的质因数去约分。这里我用的根号的质因数分解，然后二分找到最后一个素数（画蛇添足）。　　这样的话复杂度就很低了。　　~~那位29ms的大佬是什么鬼...~~

代码

//组合数+高精 #include <cstdio>#include <algorithm>#define maxl 2000#define maxn 50000#define ya 100000000ll#define ll long longusing namespace std;struct bignum{ ll num[maxl], len; bignum(){for(ll i=0;i<maxl;i++)num[i]=0;len=0;} ll& Operator[](ll x){return num[x];} void show() { printf("%lld",num[len]); for(ll i=len-1;i>0;i--) { ll x=num[i]; for(ll j=ya/10;j and num[i]<j;j/=10)putchar(48); printf("%lld",x); } }}ans;ll n, m, list[maxn], tmp[maxn] ,prime[maxn], q[maxn], mark[maxn], N, M;inline void operator*=(bignum &a, ll b){ ll i; for(i=1;i<=a.len;i++)a[i]*=b; for(i=1;i<=a.len;i++)a[i+1]+=a[i]/ya,a[i]%=ya; if(a[a.len+1])a.len++;}void shai(){ ll i, j; for(i=2;i<=N;i++) { if(!mark[i])prime[++prime[0]]=i; for(j=1;j<=prime[0] and i*prime[j]<N;j++) { mark[i*prime[j]]=1; if(i%prime[j]==0)break; } }}void resolve(ll x, ll d){ ll i, l, r, mid; for(i=1;prime[i]*prime[i]<=x;i++) for(;x%prime[i]==0;x/=prime[i])q[i]+=d; if(x==1)return; for(l=i,r=prime[0],mid=(l+r+1)>>1;l<r;mid=(l+r+1)>>1) { if(prime[mid]>x)r=mid-1; else l=mid; } q[l]+=d;}int main(){ ll i, j, t; scanf("%lld%lld",&n,&m); N=n+m-2, M=min(n-1,m-1); shai(); for(i=N-M+1;i<=N;i++)resolve(i,1); for(i=1;i<=M;i++)resolve(i,-1); ans.len=ans[1]=1; for(i=1;i<=prime[0];i++) { for(j=1,t=1;j<=q[i];j++) { if(t*prime[i]>ya) { ans*=t; t=1; } else t*=prime[i]; } if(t>1)ans*=t; } ans.show(); return 0;}

上一篇：IDEA使用技巧搜集

下一篇：整合discuz X2.5后用户免激活设置

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注