HDU 5686 斐波那契数+大数

发表于 | 分类于 | 阅读次数:
字数统计: 800 字

题目链接：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();
}