首页 > 代码库 > BZOJ 3907: 网格
BZOJ 3907: 网格
Description
求不跨过直线 \(y=x\) ,到达 \((n,m)\) 的方案数.
Sol
组合数学+高精度.
这个推导过程跟 \(Catalan\) 数是一样的.
答案就是 \(C^{n+m}_n-C^{n+m}_{n+1}\) 自己随便化简一下就是 \(\frac {(n+m)!(n-m+1)} {(n+1)!m!}\) .
然后需要先分解下质因数,再用高精度.
Code
/************************************************************** Problem: 3907 User: BeiYu Language: C++ Result: Accepted Time:108 ms Memory:1580 kb****************************************************************/ #include<cstdio>#include<cmath>#include<vector>#include<algorithm>#include<iostream>using namespace std; typedef long long LL;const int B = 10;const int W = 1; struct Big{ vector<int> s; void clear(){ s.clear(); } Big(LL num=0){ *this=num; } Big operator = (LL x){ clear(); do{ s.push_back(x%B),x/=B; }while(x); return *this; } Big operator = (const string &str){ clear(); int x,len=(str.length()-1)/W+1,l=str.length(); for(int i=0;i<len;i++){ int tt=l-i*W,st=max(0,tt-W); sscanf(str.substr(st,tt-st).c_str(),"%d",&x); s.push_back(x); }return *this;// clear();reverse(str.begin(),str.end());// int x,len=(str.length()-1)/W+1,l=str.length();// for(int i=0;i<len;i++){// int st=i,tt=min(i+W,l);// sscanf(str.substr(st,tt-st).c_str(),"%d",&x);// s.push_back(x);// }return *this; }// Big operator = (char *str){// clear();reverse(str.begin(),str.end());// int x,len=(str.length()-1)/W+1,l=str.length();// for(int i=0;i<len;i+=W){// int s=i,t=min(i+W,l);// sscanf(str(s,t-s),"%d",&x);// s.push_back(x);// }return *this;// }}; istream& operator >> (istream & in,Big &a){ string s; if(!(in>>s)) return in; a=s;return in;} ostream& operator << (ostream &out,const Big &a){ cout<<a.s.back(); for(int i=a.s.size()-2;~i;i--){ cout.width(W),cout.fill(‘0‘),cout<<a.s[i]; }return out;} bool operator < (const Big &a,const Big &b){ int la=a.s.size(),lb=b.s.size(); if(la<lb) return 1;if(la>lb) return 0; for(int i=la-1;~i;i--){ if(a.s[i]<b.s[i]) return 1; if(a.s[i]>b.s[i]) return 0; }return 0;}bool operator <= (const Big &a,const Big &b){ return !(b<a); }bool operator > (const Big &a,const Big &b){ return b<a; }bool operator >= (const Big &a,const Big &b){ return !(a<b); }bool operator == (const Big &a,const Big &b){ return !(a>b) && !(a<b); }bool operator != (const Big &a,const Big &b){ return a>b || a<b ; } Big operator + (const Big &a,const Big &b){ Big c;c.clear(); int lim=max(a.s.size(),b.s.size()),la=a.s.size(),lb=b.s.size(),i,g,x; for(i=0,g=0;;i++){ if(g==0 && i>=lim) break; x=g;if(i<la) x+=a.s[i];if(i<lb) x+=b.s[i]; c.s.push_back(x%B),g=x/B; }i=c.s.size()-1; while(c.s[i]==0 && i) c.s.pop_back(),i--; return c;}Big operator - (const Big &a,const Big &b){ Big c;c.clear(); int i,g,x,la=a.s.size(),lb=b.s.size(); for(i=0,g=0;i<la;i++){ x=a.s[i]-g; if(i<lb) x-=b.s[i]; if(x>=0) g=0;else g=1,x+=B; c.s.push_back(x); }i=c.s.size()-1; while(c.s[i]==0 && i) c.s.pop_back(),i--; return c;}Big operator * (const Big &a,const Big &b){ Big c; int i,j,la=a.s.size(),lb=b.s.size(),lc=la+lb; c.s.resize(lc,0); for(i=0;i<la;i++) for(j=0;j<lb;j++) c.s[i+j]+=a.s[i]*b.s[j]; for(i=0;i<lc;i++) c.s[i+1]+=c.s[i]/B,c.s[i]%=B; i=lc-1;while(c.s[i]==0 && i) c.s.pop_back(),i--; return c;}Big operator / (const Big &a,const Big &b){ Big c,f=0; int la=a.s.size(),i; c.s.resize(la,0); for(i=la-1;~i;i--){ f=f*B,f.s[0]=a.s[i]; while(f>=b) f=f-b,c.s[i]++; }i=la-1;while(c.s[i]==0 && i) c.s.pop_back(),i--; return c;}Big operator % (const Big &a,const Big &b){ Big c=a-(a/b)*b; return c;}Big operator ^ (Big &a,Big &b){ Big c=1; for(;b!=0;b=b/2,a=a*a){ if(b.s[0] & 1) c=c*a; }return c;}Big operator += (Big &a,const Big &b){ return a=a+b; }Big operator -= (Big &a,const Big &b){ return a=a-b; }Big operator *= (Big &a,const Big &b){ return a=a*b; }Big operator /= (Big &a,const Big &b){ return a=a/b; }Big operator %= (Big &a,const Big &b){ return a=a%b; } const int N = 10005; int cnt;int b[N],pr[N],minp[N],c[N]; void Pre(int t){ minp[1]=0; for(int i=2;i<=t;i++){ if(!b[i]) pr[++cnt]=i,minp[i]=cnt; for(int j=1;j<=cnt && i*pr[j]<=t;j++){ b[i*pr[j]]=1,minp[i*pr[j]]=j; if(i%pr[j]==0) break; } }}void Add(int x,int v){ while(x>1) c[minp[x]]+=v,x/=pr[minp[x]]; }int main(){ ios::sync_with_stdio(false);// cout<<"qwq"<<endl; int n,m;Big a=1,b,d; cin>>n>>m; Pre(n+m);// cout<<"qwq"<<endl;// cout<<cnt<<endl;// for(int i=1;i<=cnt;i++) cout<<pr[i]<<" ";cout<<endl; for(int i=n+2;i<=n+m;i++) Add(i,1); Add(n-m+1,1); for(int i=1;i<=m;i++) Add(i,-1); for(int i=1;i<=cnt;i++){ b=pr[i],d=c[i],a*=b^d;// cout<<b;cout<<" ";cout<<d;cout<<" ";cout<<(b^d);cout<<endl; } cout<<a<<endl; return 0;}
BZOJ 3907: 网格
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。