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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1005][HNOI2008]明明的烦恼  

2014-05-07 15:45:10|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
prufer编码 + 组合数学
恩还好GTY告诉我是没学过的奇怪东西,要不然又要陷入深坑Orz

/*
prufer编码 + 组合数学
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N = 10000+1;
const int _MAX = 10000+1;
int n,m,pri[N],tot,rd[N],all;
int pnum[N],add[N];
bool v[N];
const int L = 100000000;
void getpri(int nn){
int i,j;
for(i=2;i<=nn;i++){
if(!v[i])pri[++pri[0]]=i;
for(j=1;j<=pri[0]&&pri[j]*i<=nn;j++){
v[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
}
void getadd(int d,int k,int fh){
for(int i=1;i<=pri[0]&&d>1&&pri[i]<=d;i++){
int j=0;
while(d%pri[i]==0)d/=pri[i],j++;
pnum[i]+=j*k*fh;
}
}
void getjc(int d,int fh){
if(d<=1) return;
for(int i=1;i<=pri[0];i++){
int p=pri[i];
for(;p<=d;p*=pri[i])
pnum[i]+=d/p*fh;
}
}
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\n'||cc=='\r')cc=getchar();
if(cc=='+'){fh=1;cc=getchar();}
if(cc=='-'){fh=-1;cc=getchar();}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
void putint(long long x){
if(x<10)
putchar(x+'0');
else{
putint(x/10);
putchar(x%10+'0');
}
}
void putput(long long x,int len){
if(len==1)
putchar(x+'0');
else{
putput(x/10,len-1);
putchar(x%10+'0');
}
}
struct Big{
long long d[400];
Big(){memset(d,0,sizeof(d));}
Big(int x){
*this=Big();
if(x==0){d[0]=1;d[1]=0;}
for(;x;x/=L) d[++d[0]]=x%L;
}
void print(){
//printf("%lld",d[d[0]]);
putint(d[d[0]]);
for(int i=d[0]-1;i>=1;i--)
putput(d[i],8);
//printf("%08lld",d[i]);
}
}ans;
Big operator * (const Big &a,const Big &b){
Big c;
c.d[0]=a.d[0]+b.d[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]>=L){
c.d[i+1]+=c.d[i]/L;
c.d[i]%=L;
}
while(c.d[c.d[0]]==0&&c.d[0]>1)c.d[0]--;
return c;
}
Big pow(Big a,int k){
Big re=Big(1);
for(;k;k>>=1,a=a*a)
if(k&1) re=re*a;
return re;
}
int main(){
int i,j;
//printf(" ");
//freopen("input.txt","r",stdin);
getpri(n=scan());
for(i=1;i<=n;i++){
if((rd[i]=scan())!=-1) tot+=rd[i],all++;
if(rd[i]==0){
printf("0\n");
return 0;
}
}
if(tot>(n-1)*2||(tot<(n-1)*2&&all==n)||(tot==(n-1)*2&&all<n)){
printf("0\n");
return 0;
}
tot-=all;
all=n-all;

getjc(n-2,1);
if(n-2-tot>0)getadd(all,n-2-tot,1);

getjc(n-2-tot,-1);
for(i=1;i<=pri[0];i++)
if(rd[i]>0)
getjc(rd[i]-1,-1);
ans=Big(1);
for(i=1;i<=n;i++)
if(pnum[i])
ans=ans*pow(Big(pri[i]),pnum[i]);
ans.print();
return 0;
}


  评论这张
 
阅读(10)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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