注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3907]网格  

2015-03-20 17:52:04|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3907: 网格

传说中的拓展卡特兰数
问题相当于求(((?????的合法方案数

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int LEN = 10000;
const int N = 5100*2;//!!!
int n,m,pri[N],pos[N],cot[N];
short v[N];
struct Num{
int d[10100];
void print(){printf("%d",d[d[0]]);for(int i=d[0]-1;i;i--)printf("%04d",d[i]);}
Num(int x=0){for(d[0]=0;x;x/=LEN)d[++d[0]]=x%LEN;if(d[0]==0)d[(d[0]=1)]=0;}
}ans,tmp;

Num operator * (const Num&a,const Num&b){
Num c;
c.d[0] = a.d[0] + b.d[0];
for(int i=1;i<=c.d[0];i++)c.d[i]=0;
for(int i=1;i<=a.d[0];i++)
for(int j=1;j<=b.d[0];j++){
c.d[i+j-1] += a.d[i]*b.d[j];
}
for(int i=1;i<=c.d[0];i++)
if(c.d[i] >= LEN){
c.d[i+1] += c.d[i]/LEN;
c.d[i]%=LEN;
}
while(c.d[0]>1 && c.d[c.d[0]]==0)c.d[0]--;
return c;
}
Num kpow(Num x,int k){
Num re(1);
for(;k;k/=2,x=x*x)
if(k&1)re=re*x;
return re;
}
void getpri(int n){
int i,j;
for(i=2;i<=n;i++){
if(!v[i]){
pri[++pri[0]] = i;
pos[i]=pri[0];
}
for(j=1;j<=pri[0]&&i*pri[j]<=n;j++){
v[i*pri[j]]=1;
if(i%pri[j]==0)break;
}
}
}
void add(int x,short t){
if(!v[x]){cot[pos[x]]+=t;return;}
for(int i=1;i<=pri[0]&&pri[i]*pri[i]<=x;i++)
while(x%pri[i]==0){
cot[i]+=t;
x/=pri[i];
}
if(x > 1)cot[pos[x]]+=t;
}
Num C(int n,int m){
Num re(1);
for(int i=0;i<m;i++){
add(n-i,+1);
add(i+1,-1);
}
for(int i=1;i<=pri[0];i++)
re = re*kpow(pri[i],cot[i]),cot[i]=0;
return re;
}
Num operator - (Num&a,Num &b){
Num c;
c.d[0] = max(a.d[0],b.d[0]);
for(int i=1;i<=c.d[0];i++){
c.d[i]=0;
if(i > a.d[0])a.d[i]=0;
if(i > b.d[0])b.d[i]=0;
}
for(int i=1;i<=c.d[0];i++){
c.d[i] += a.d[i]-b.d[i];
if(c.d[i]<0){
c.d[i]+=LEN;
c.d[i+1]-=1;
}
}
while(c.d[0]>1 && c.d[c.d[0]]==0)c.d[0]--;
return c;
}
int main(){
int i,j,t;
scanf("%d%d",&n,&m);
n++;
getpri(n+m);
ans = C(n+m,m);
tmp = C(n+m-1,m-1);
ans = ans-tmp;
ans = ans-tmp;
ans.print();
return 0;
}

题解:
不碰线的版本:
ans = C(n+m,m)-2*C(n+m-1,m-1)
2*是因为第一步向右走的不合法方案可以由第一步向上走的不合法方案对称得到。
可以碰线的话就是平移一下:
把n+1就好了
  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017