2016"百度之星" - 资格赛（Astar Round1） B
2024-08-24 04:01:15
Problem Description
度熊面前有一个全是由1构成的字符串，被称为全1序列。你可以合并任意相邻的两个1，从而形成一个新的序列。对于给定的一个全1序列，请计算根据以上方法，可以构成多少种不同的序列。
Input
这里包括多组测试数据，每组测试数据包含一个正整数NN，代表全1序列的长度。
1≤N≤200
Output
对于每组测试数据，输出一个整数，代表由题目中所给定的全1序列所能形成的新序列的数量。
Sample Input
1
3
5
Sample Output
1
3
8
Hint
如果序列是：(111)。可以构造出如下三个新序列：(111), (21), (12)。
仔细写一下，是一个斐波那契数列哦，当然要有大数（存在n==0）不要输出，换行就行！
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std; #define DIGIT 4 //四位隔开,即万进制
#define DEPTH 10000 //万进制
#define MAX 100 //题目最大位数/4，要不大直接设为最大位数也行
typedef int bignum_t[MAX+]; /************************************************************************/
/* 读取操作数，对操作数进行处理存储在数组里 */
/************************************************************************/
int read(bignum_t a,istream&is=cin)
{
char buf[MAX*DIGIT+],ch ;
int i,j ;
memset((void*)a,,sizeof(bignum_t));
if(!(is>>buf))return ;
for(a[]=strlen(buf),i=a[]/-;i>=;i--)
ch=buf[i],buf[i]=buf[a[]--i],buf[a[]--i]=ch ;
for(a[]=(a[]+DIGIT-)/DIGIT,j=strlen(buf);j<a[]*DIGIT;buf[j++]='');
for(i=;i<=a[];i++)
for(a[i]=,j=;j<DIGIT;j++)
a[i]=a[i]*+buf[i*DIGIT--j]-'' ;
for(;!a[a[]]&&a[]>;a[]--);
return ;
} void write(const bignum_t a,ostream&os=cout)
{
int i,j ;
for(os<<a[i=a[]],i--;i;i--)
for(j=DEPTH/;j;j/=)
os<<a[i]/j% ;
} int comp(const bignum_t a,const bignum_t b)
{
int i ;
if(a[]!=b[])
return a[]-b[];
for(i=a[];i;i--)
if(a[i]!=b[i])
return a[i]-b[i];
return ;
} int comp(const bignum_t a,const int b)
{
int c[]=
{
}
;
for(c[]=b;c[c[]]>=DEPTH;c[c[]+]=c[c[]]/DEPTH,c[c[]]%=DEPTH,c[]++);
return comp(a,c);
} int comp(const bignum_t a,const int c,const int d,const bignum_t b)
{
int i,t=,O=-DEPTH* ;
if(b[]-a[]<d&&c)
return ;
for(i=b[];i>d;i--)
{
t=t*DEPTH+a[i-d]*c-b[i];
if(t>)return ;
if(t<O)return ;
}
for(i=d;i;i--)
{
t=t*DEPTH-b[i];
if(t>)return ;
if(t<O)return ;
}
return t> ;
}
/************************************************************************/
/* 大数与大数相加 */
/************************************************************************/
void add(bignum_t a,const bignum_t b)
{
int i ;
for(i=;i<=b[];i++)
if((a[i]+=b[i])>=DEPTH)
a[i]-=DEPTH,a[i+]++;
if(b[]>=a[])
a[]=b[];
else
for(;a[i]>=DEPTH&&i<a[];a[i]-=DEPTH,i++,a[i]++);
a[]+=(a[a[]+]>);
}
/************************************************************************/
/* 大数与小数相加 */
/************************************************************************/
void add(bignum_t a,const int b)
{
int i= ;
for(a[]+=b;a[i]>=DEPTH&&i<a[];a[i+]+=a[i]/DEPTH,a[i]%=DEPTH,i++);
for(;a[a[]]>=DEPTH;a[a[]+]=a[a[]]/DEPTH,a[a[]]%=DEPTH,a[]++);
}
/************************************************************************/
/* 大数相减(被减数>=减数) */
/************************************************************************/
void sub(bignum_t a,const bignum_t b)
{
int i ;
for(i=;i<=b[];i++)
if((a[i]-=b[i])<)
a[i+]--,a[i]+=DEPTH ;
for(;a[i]<;a[i]+=DEPTH,i++,a[i]--);
for(;!a[a[]]&&a[]>;a[]--);
}
/************************************************************************/
/* 大数减去小数(被减数>=减数) */
/************************************************************************/
void sub(bignum_t a,const int b)
{
int i= ;
for(a[]-=b;a[i]<;a[i+]+=(a[i]-DEPTH+)/DEPTH,a[i]-=(a[i]-DEPTH+)/DEPTH*DEPTH,i++);
for(;!a[a[]]&&a[]>;a[]--);
} void sub(bignum_t a,const bignum_t b,const int c,const int d)
{
int i,O=b[]+d ;
for(i=+d;i<=O;i++)
if((a[i]-=b[i-d]*c)<)
a[i+]+=(a[i]-DEPTH+)/DEPTH,a[i]-=(a[i]-DEPTH+)/DEPTH*DEPTH ;
for(;a[i]<;a[i+]+=(a[i]-DEPTH+)/DEPTH,a[i]-=(a[i]-DEPTH+)/DEPTH*DEPTH,i++);
for(;!a[a[]]&&a[]>;a[]--);
}
/************************************************************************/
/* 大数相乘，读入被乘数a，乘数b，结果保存在c[] */
/************************************************************************/
void mul(bignum_t c,const bignum_t a,const bignum_t b)
{
int i,j ;
memset((void*)c,,sizeof(bignum_t));
for(c[]=a[]+b[]-,i=;i<=a[];i++)
for(j=;j<=b[];j++)
if((c[i+j-]+=a[i]*b[j])>=DEPTH)
c[i+j]+=c[i+j-]/DEPTH,c[i+j-]%=DEPTH ;
for(c[]+=(c[c[]+]>);!c[c[]]&&c[]>;c[]--);
}
/************************************************************************/
/* 大数乘以小数，读入被乘数a，乘数b，结果保存在被乘数 */
/************************************************************************/
void mul(bignum_t a,const int b)
{
int i ;
for(a[]*=b,i=;i<=a[];i++)
{
a[i]*=b ;
if(a[i-]>=DEPTH)
a[i]+=a[i-]/DEPTH,a[i-]%=DEPTH ;
}
for(;a[a[]]>=DEPTH;a[a[]+]=a[a[]]/DEPTH,a[a[]]%=DEPTH,a[]++);
for(;!a[a[]]&&a[]>;a[]--);
} void mul(bignum_t b,const bignum_t a,const int c,const int d)
{
int i ;
memset((void*)b,,sizeof(bignum_t));
for(b[]=a[]+d,i=d+;i<=b[];i++)
if((b[i]+=a[i-d]*c)>=DEPTH)
b[i+]+=b[i]/DEPTH,b[i]%=DEPTH ;
for(;b[b[]+];b[]++,b[b[]+]=b[b[]]/DEPTH,b[b[]]%=DEPTH);
for(;!b[b[]]&&b[]>;b[]--);
}
/**************************************************************************/
/* 大数相除,读入被除数a，除数b，结果保存在c[]数组 */
/* 需要comp()函数 */
/**************************************************************************/
void div(bignum_t c,bignum_t a,const bignum_t b)
{
int h,l,m,i ;
memset((void*)c,,sizeof(bignum_t));
c[]=(b[]<a[]+)?(a[]-b[]+): ;
for(i=c[];i;sub(a,b,c[i]=m,i-),i--)
for(h=DEPTH-,l=,m=(h+l+)>>;h>l;m=(h+l+)>>)
if(comp(b,m,i-,a))h=m- ;
else l=m ;
for(;!c[c[]]&&c[]>;c[]--);
c[]=c[]>?c[]: ;
} void div(bignum_t a,const int b,int&c)
{
int i ;
for(c=,i=a[];i;c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--);
for(;!a[a[]]&&a[]>;a[]--);
}
/************************************************************************/
/* 大数平方根，读入大数a，结果保存在b[]数组里 */
/* 需要comp()函数 */
/************************************************************************/
void sqrt(bignum_t b,bignum_t a)
{
int h,l,m,i ;
memset((void*)b,,sizeof(bignum_t));
for(i=b[]=(a[]+)>>;i;sub(a,b,m,i-),b[i]+=m,i--)
for(h=DEPTH-,l=,b[i]=m=(h+l+)>>;h>l;b[i]=m=(h+l+)>>)
if(comp(b,m,i-,a))h=m- ;
else l=m ;
for(;!b[b[]]&&b[]>;b[]--);
for(i=;i<=b[];b[i++]>>=);
}
/************************************************************************/
/* 返回大数的长度 */
/************************************************************************/
int length(const bignum_t a)
{
int t,ret ;
for(ret=(a[]-)*DIGIT,t=a[a[]];t;t/=,ret++);
return ret>?ret: ;
}
/************************************************************************/
/* 返回指定位置的数字，从低位开始数到第b位，返回b位上的数 */
/************************************************************************/
int digit(const bignum_t a,const int b)
{
int i,ret ;
for(ret=a[(b-)/DIGIT+],i=(b-)%DIGIT;i;ret/=,i--);
return ret% ;
}
/************************************************************************/
/* 返回大数末尾0的个数 */
/************************************************************************/
int zeronum(const bignum_t a)
{
int ret,t ;
for(ret=;!a[ret+];ret++);
for(t=a[ret+],ret*=DIGIT;!(t%);t/=,ret++);
return ret ;
} void comp(int*a,const int l,const int h,const int d)
{
int i,j,t ;
for(i=l;i<=h;i++)
for(t=i,j=;t>;j++)
while(!(t%j))
a[j]+=d,t/=j ;
} void convert(int*a,const int h,bignum_t b)
{
int i,j,t= ;
memset(b,,sizeof(bignum_t));
for(b[]=b[]=,i=;i<=h;i++)
if(a[i])
for(j=a[i];j;t*=i,j--)
if(t*i>DEPTH)
mul(b,t),t= ;
mul(b,t);
}
/************************************************************************/
/* 组合数 */
/************************************************************************/
void combination(bignum_t a,int m,int n)
{
int*t=new int[m+];
memset((void*)t,,sizeof(int)*(m+));
comp(t,n+,m,);
comp(t,,m-n,-);
convert(t,m,a);
delete[]t ;
}
/************************************************************************/
/* 排列数 */
/************************************************************************/
void permutation(bignum_t a,int m,int n)
{
int i,t= ;
memset(a,,sizeof(bignum_t));
a[]=a[]= ;
for(i=m-n+;i<=m;t*=i++)
if(t*i>DEPTH)
mul(a,t),t= ;
mul(a,t);
} #define SGN(x) ((x)>0?1:((x)<0?-1:0))
#define ABS(x) ((x)>0?(x):-(x)) int read(bignum_t a,int&sgn,istream&is=cin)
{
char str[MAX*DIGIT+],ch,*buf ;
int i,j ;
memset((void*)a,,sizeof(bignum_t));
if(!(is>>str))return ;
buf=str,sgn= ;
if(*buf=='-')sgn=-,buf++;
for(a[]=strlen(buf),i=a[]/-;i>=;i--)
ch=buf[i],buf[i]=buf[a[]--i],buf[a[]--i]=ch ;
for(a[]=(a[]+DIGIT-)/DIGIT,j=strlen(buf);j<a[]*DIGIT;buf[j++]='');
for(i=;i<=a[];i++)
for(a[i]=,j=;j<DIGIT;j++)
a[i]=a[i]*+buf[i*DIGIT--j]-'' ;
for(;!a[a[]]&&a[]>;a[]--);
if(a[]==&&!a[])sgn= ;
return ;
}
struct bignum
{
bignum_t num ;
int sgn ;
public :
inline bignum()
{
memset(num,,sizeof(bignum_t));
num[]= ;
sgn= ;
}
inline int operator!()
{
return num[]==&&!num[];
}
inline bignum&operator=(const bignum&a)
{
memcpy(num,a.num,sizeof(bignum_t));
sgn=a.sgn ;
return*this ;
}
inline bignum&operator=(const int a)
{
memset(num,,sizeof(bignum_t));
num[]= ;
sgn=SGN (a);
add(num,sgn*a);
return*this ;
}
;
inline bignum&operator+=(const bignum&a)
{
if(sgn==a.sgn)add(num,a.num);
else if
(sgn&&a.sgn)
{
int ret=comp(num,a.num);
if(ret>)sub(num,a.num);
else if(ret<)
{
bignum_t t ;
memcpy(t,num,sizeof(bignum_t));
memcpy(num,a.num,sizeof(bignum_t));
sub (num,t);
sgn=a.sgn ;
}
else memset(num,,sizeof(bignum_t)),num[]=,sgn= ;
}
else if(!sgn)
memcpy(num,a.num,sizeof(bignum_t)),sgn=a.sgn ;
return*this ;
}
inline bignum&operator+=(const int a)
{
if(sgn*a>)add(num,ABS(a));
else if(sgn&&a)
{
int ret=comp(num,ABS(a));
if(ret>)sub(num,ABS(a));
else if(ret<)
{
bignum_t t ;
memcpy(t,num,sizeof(bignum_t));
memset(num,,sizeof(bignum_t));
num[]= ;
add(num,ABS (a));
sgn=-sgn ;
sub(num,t);
}
else memset(num,,sizeof(bignum_t)),num[]=,sgn= ;
}
else if
(!sgn)sgn=SGN(a),add(num,ABS(a));
return*this ;
}
inline bignum operator+(const bignum&a)
{
bignum ret ;
memcpy(ret.num,num,sizeof (bignum_t));
ret.sgn=sgn ;
ret+=a ;
return ret ;
}
inline bignum operator+(const int a)
{
bignum ret ;
memcpy(ret.num,num,sizeof (bignum_t));
ret.sgn=sgn ;
ret+=a ;
return ret ;
}
inline bignum&operator-=(const bignum&a)
{
if(sgn*a.sgn<)add(num,a.num);
else if
(sgn&&a.sgn)
{
int ret=comp(num,a.num);
if(ret>)sub(num,a.num);
else if(ret<)
{
bignum_t t ;
memcpy(t,num,sizeof(bignum_t));
memcpy(num,a.num,sizeof(bignum_t));
sub(num,t);
sgn=-sgn ;
}
else memset(num,,sizeof(bignum_t)),num[]=,sgn= ;
}
else if(!sgn)add (num,a.num),sgn=-a.sgn ;
return*this ;
}
inline bignum&operator-=(const int a)
{
if(sgn*a<)add(num,ABS(a));
else if(sgn&&a)
{
int ret=comp(num,ABS(a));
if(ret>)sub(num,ABS(a));
else if(ret<)
{
bignum_t t ;
memcpy(t,num,sizeof(bignum_t));
memset(num,,sizeof(bignum_t));
num[]= ;
add(num,ABS(a));
sub(num,t);
sgn=-sgn ;
}
else memset(num,,sizeof(bignum_t)),num[]=,sgn= ;
}
else if
(!sgn)sgn=-SGN(a),add(num,ABS(a));
return*this ;
}
inline bignum operator-(const bignum&a)
{
bignum ret ;
memcpy(ret.num,num,sizeof(bignum_t));
ret.sgn=sgn ;
ret-=a ;
return ret ;
}
inline bignum operator-(const int a)
{
bignum ret ;
memcpy(ret.num,num,sizeof(bignum_t));
ret.sgn=sgn ;
ret-=a ;
return ret ;
}
inline bignum&operator*=(const bignum&a)
{
bignum_t t ;
mul(t,num,a.num);
memcpy(num,t,sizeof(bignum_t));
sgn*=a.sgn ;
return*this ;
}
inline bignum&operator*=(const int a)
{
mul(num,ABS(a));
sgn*=SGN(a);
return*this ;
}
inline bignum operator*(const bignum&a)
{
bignum ret ;
mul(ret.num,num,a.num);
ret.sgn=sgn*a.sgn ;
return ret ;
}
inline bignum operator*(const int a)
{
bignum ret ;
memcpy(ret.num,num,sizeof (bignum_t));
mul(ret.num,ABS(a));
ret.sgn=sgn*SGN(a);
return ret ;
}
inline bignum&operator/=(const bignum&a)
{
bignum_t t ;
div(t,num,a.num);
memcpy (num,t,sizeof(bignum_t));
sgn=(num[]==&&!num[])?:sgn*a.sgn ;
return*this ;
}
inline bignum&operator/=(const int a)
{
int t ;
div(num,ABS(a),t);
sgn=(num[]==&&!num [])?:sgn*SGN(a);
return*this ;
}
inline bignum operator/(const bignum&a)
{
bignum ret ;
bignum_t t ;
memcpy(t,num,sizeof(bignum_t));
div(ret.num,t,a.num);
ret.sgn=(ret.num[]==&&!ret.num[])?:sgn*a.sgn ;
return ret ;
}
inline bignum operator/(const int a)
{
bignum ret ;
int t ;
memcpy(ret.num,num,sizeof(bignum_t));
div(ret.num,ABS(a),t);
ret.sgn=(ret.num[]==&&!ret.num[])?:sgn*SGN(a);
return ret ;
}
inline bignum&operator%=(const bignum&a)
{
bignum_t t ;
div(t,num,a.num);
if(num[]==&&!num[])sgn= ;
return*this ;
}
inline int operator%=(const int a)
{
int t ;
div(num,ABS(a),t);
memset(num,,sizeof (bignum_t));
num[]= ;
add(num,t);
return t ;
}
inline bignum operator%(const bignum&a)
{
bignum ret ;
bignum_t t ;
memcpy(ret.num,num,sizeof(bignum_t));
div(t,ret.num,a.num);
ret.sgn=(ret.num[]==&&!ret.num [])?:sgn ;
return ret ;
}
inline int operator%(const int a)
{
bignum ret ;
int t ;
memcpy(ret.num,num,sizeof(bignum_t));
div(ret.num,ABS(a),t);
memset(ret.num,,sizeof(bignum_t));
ret.num[]= ;
add(ret.num,t);
return t ;
}
inline bignum&operator++()
{
*this+= ;
return*this ;
}
inline bignum&operator--()
{
*this-= ;
return*this ;
}
;
inline int operator>(const bignum&a)
{
return sgn>?(a.sgn>?comp(num,a.num)>:):(sgn<?(a.sgn<?comp(num,a.num)<:):a.sgn<);
}
inline int operator>(const int a)
{
return sgn>?(a>?comp(num,a)>:):(sgn<?(a<?comp(num,-a)<:):a<);
}
inline int operator>=(const bignum&a)
{
return sgn>?(a.sgn>?comp(num,a.num)>=:):(sgn<?(a.sgn<?comp(num,a.num)<=:):a.sgn<=);
}
inline int operator>=(const int a)
{
return sgn>?(a>?comp(num,a)>=:):(sgn<?(a<?comp(num,-a)<=:):a<=);
}
inline int operator<(const bignum&a)
{
return sgn<?(a.sgn<?comp(num,a.num)>:):(sgn>?(a.sgn>?comp(num,a.num)<:):a.sgn>);
}
inline int operator<(const int a)
{
return sgn<?(a<?comp(num,-a)>:):(sgn>?(a>?comp(num,a)<:):a>);
}
inline int operator<=(const bignum&a)
{
return sgn<?(a.sgn<?comp(num,a.num)>=:):(sgn>?(a.sgn>?comp(num,a.num)<=:):a.sgn>=);
}
inline int operator<=(const int a)
{
return sgn<?(a<?comp(num,-a)>=:):
(sgn>?(a>?comp(num,a)<=:):a>=);
}
inline int operator==(const bignum&a)
{
return(sgn==a.sgn)?!comp(num,a.num): ;
}
inline int operator==(const int a)
{
return(sgn*a>=)?!comp(num,ABS(a)): ;
}
inline int operator!=(const bignum&a)
{
return(sgn==a.sgn)?comp(num,a.num): ;
}
inline int operator!=(const int a)
{
return(sgn*a>=)?comp(num,ABS(a)): ;
}
inline int operator[](const int a)
{
return digit(num,a);
}
friend inline istream&operator>>(istream&is,bignum&a)
{
read(a.num,a.sgn,is);
return is ;
}
friend inline ostream&operator<<(ostream&os,const bignum&a)
{
if(a.sgn<)
os<<'-' ;
write(a.num,os);
return os ;
}
friend inline bignum sqrt(const bignum&a)
{
bignum ret ;
bignum_t t ;
memcpy(t,a.num,sizeof(bignum_t));
sqrt(ret.num,t);
ret.sgn=ret.num[]!=||ret.num[];
return ret ;
}
friend inline bignum sqrt(const bignum&a,bignum&b)
{
bignum ret ;
memcpy(b.num,a.num,sizeof(bignum_t));
sqrt(ret.num,b.num);
ret.sgn=ret.num[]!=||ret.num[];
b.sgn=b.num[]!=||ret.num[];
return ret ;
}
inline int length()
{
return :: length(num);
}
inline int zeronum()
{
return :: zeronum(num);
}
inline bignum C(const int m,const int n)
{
combination(num,m,n);
sgn= ;
return*this ;
}
inline bignum P(const int m,const int n)
{
permutation(num,m,n);
sgn= ;
return*this ;
}
};
int main()
{
bignum a[];
a[]=;
a[]=;
int n;
for(int i=;i<=;i++)
{
a[i]=a[i-]+a[i-];
}
while(cin>>n)
{
if(n==0)
cout<<"\n";
else
cout<<a[n]<<endl;
}
return ;
}
最新文章
- 浏览器版本不支持页面示例 supper.html
- Xcode 6制作动态及静态Framework
- vertica 8.0 新特性
- Win8&Win2012R2如何支持DOTA2输入法
- JS/React 判断对象是否为空对象
- php接收数据
- Sphinx 全文检索
- Spring 使用注解方式进行事物管理
- linux的7种运行级别<学习笔记>
- 线上应用故障排查之一：高CPU占用
- BZOJ 1565: [NOI2009]植物大战僵尸( 最小割 )
- SVN第二篇-----命令集合
- 给xcode项目修改名字
- abap 变量检查
- Linux（CentOS）安装Node.JS和npm的两种方式（yum安装和源码安装）
- 剑指offer——python【第36题】两个链表的第一个公共结点
- web基础，用html元素制作web页面
- C++重载>>和<<（输入输出运算符）
- class 方法
- 【C++】atoi与stoi