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
#include
#include
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[]--);
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[]
{
t=t*DEPTH+a[i-d]*c-b[i];
if(t>)return ;
if(t
if(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);
}
/************************************************************************/
/* 大数与小数相加 */
/************************************************************************/
void add(bignum_t a,const int b)
{
int i= ;
for(a[]+=b;a[i]>=DEPTH&&i=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[]>;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))
手机扫一扫
移动阅读更方便
你可能感兴趣的文章