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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1089] [SCOI2003]严格n元树  

2014-05-09 07:01:44|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@[BZOJ1089] [SCOI2003]严格n元树
还算比较水的题
DP+高精度
递推式也不难想

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int L = 10000;
const int N = 16+1;
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;
}
int n,m;
struct Big{
int d[10000+1];
Big(){memset(d,0,sizeof(d));d[0]=1;}
Big(int x){
*this=Big();
if(x==0){d[0]=1;d[1]=0;}
for(d[0]=0;x;x/=L)
d[++d[0]]=x%L;
}
void print(){
printf("%d",d[d[0]]);
for(int i=d[0]-1;i;i--)
printf("%04d",d[i]);
}
}f[4],sum[4];
Big operator * (const Big &a,const Big &b){
Big c;int i,j;
if(a.d[0]==1&&a.d[1]==1) return b;
if(b.d[0]==1&&b.d[1]==1) return a;
c.d[0]=a.d[0]+b.d[0];
for(i=1;i<=a.d[0];i++)
for(j=1;j<=b.d[0];j++)
c.d[i+j-1]+=a.d[i]*b.d[j];
for(i=1;i<=c.d[0];i++){
c.d[i+1]+=c.d[i]/L;
c.d[i]%=L;
}
while(c.d[0]>1&&c.d[c.d[0]]==0)c.d[0]--;
return c;
}
Big operator + (const Big &a,const Big &b){
Big c;
c.d[0]=max(a.d[0],b.d[0])+1;
for(int i=1;i<=c.d[0];i++){
c.d[i]+=a.d[i]+b.d[i];
c.d[i+1]=c.d[i]/L;
c.d[i]%=L;
}
if(c.d[0]>1&&c.d[c.d[0]]==0)c.d[0]--;
return c;
}
//a > b
Big operator - (const Big &a,const Big &b){
Big c;
c.d[0]=max(a.d[0],b.d[0])+1;
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]+=L;
c.d[i+1]-=1;
}
}
while(c.d[0]>1&&c.d[c.d[0]]==0)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(){
Big aa;
//freopen("input.txt","r",stdin);
int i,j;
n=scan();m=scan();
f[0]=sum[0]=f[1]=Big(1);
sum[1]=Big(2);
for(i=2;i<=m;i++){
f[i%4]=pow(sum[(i-1)%4],n)-pow(sum[(i-2)%4],n);
sum[i%4]=sum[(i-1)%4]+f[i%4];
}
f[m%4].print();
printf("\n");
return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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