HDU 5686 斐波那契数+大数

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5686

题意

有一个全部是1组成的序列,可以合并相邻的两个1,变成一个新的序列。问总共可以构成多少种不同的序列。序列长度范围为200

题解

这道题其实列出前几个数的答案可以观察得到是一个斐波那契数,当然也可以按照下面这种方式进行理解:
一个序列的组合方式可以分成两种情况:第一种情况是最后一个数不考虑那么相当于前面的n-1个数的排列种树;第二种情况将最后两个数合并这样就相当于前面n-2个数的排列情况
斐波那契数到达200个数,要使用大数模板,套上用就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
struct BigInt
{
const static int nlen=4; //控制数组中的每一个数字的长度,为了乘法运算不溢出设定为4
const static int mod=10000; //每个数字大小设定
short n[1000],len; //存放数字的数组以及数组的长度
BigInt()//没有赋值时初始化为0
{
memset(n,0,sizeof(n));
len=1;
}
BigInt(int num)//数字为其赋值时,将数字4位4位存放在数组当中
{
len=0;
while(num>0)
{
n[len++]=num%mod;
num/=mod;
}
}
BigInt(const char *s) //字符串赋值时
{
int l=strlen(s);
len=l%nlen==0?l/nlen:l/nlen+1;//确定数组长度
int index=0;
for(int i=l-1;i>=0;i-=nlen)//每次处理数组中的一位
{
int tmp=0;
int j=i-nlen+1;
if(j<0) j=0;//最后面数字的处理
for(int k=j;k<=i;k++)
tmp=tmp*10+s[k]-'0';
n[index++]=tmp;
}
}
BigInt operator+(const BigInt &b)const //加法操作
{
BigInt res;
res.len=max(len,b.len); //确定位数
for(int i=0;i<res.len;i++)
{
res.n[i]+=(i<len?n[i]:0)+(i<b.len?b.n[i]:0); //对象位置相加
res.n[i+1]+=res.n[i]/mod; //进位处理
res.n[i]=res.n[i]%mod;
}
if(res.n[res.len]>0)res.len++; //最后的结果多出一位时
return res;
}
BigInt operator*(const BigInt &b)const //乘法操作
{
BigInt res;
for(int i=0;i<len;i++) //模拟过程
{
int up=0; //进位存储
for(int j=0;j<b.len;j++)
{
int tmp=n[i]*b.n[i]+up+res.n[i+j];
res.n[i+j]=tmp%mod;
up=tmp/mod;
}
if(up!=0) //处理一遍以后还有进位
res.n[i+b.len]=up;
}
res.len=len+b.len; //先取到位数可能最大的值
while(res.n[res.len-1]==0&&res.len>1)res.len--;
return res;
}
void show() const //输出时的逆序输出
{
printf("%d",n[len-1]);
for(int i=len-2;i>=0;i--)
printf("%04d",n[i]); //注意一定要加04,确保输出四位
printf("\n");
}
};
void solve()
{
BigInt a[210];
a[1]=1;
a[2]=2;
for(int i=3;i<201;i++)
a[i]=a[i-1]+a[i-2];
int n;
while(scanf("%d",&n)!=EOF)
a[n].show();
}