You will be given a string which only contains ‘1’; You can merge two adjacent ‘1’ to be ‘2’, or leave the ‘1’ there. Surly, you may get many different results. For example, given 1111 , you can get 1111, 121, 112,211,22. Now, your
work is to find the total number of result you can get.

The first line is a number n refers to the number of test cases. Then n lines follows, each line has a string made up of ‘1’ . The maximum length of the sequence is 200.

The output contain n lines, each line output the number of result you can get .

3
1
11
11111

1
2
8


解题思路：
	一开始还以为要用组合数学来做了。。
	后来发现原来是个斐波那契数列。
	悲剧的是将200的字符串长度看成了20。。。 硬生生的把一道高精度加法当做了简单加法做。。

算法：
	高精度计算。

代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[201][101]={0};
int main ()
{
    int n,i,j;
    a[1][100]=1;
    a[2][100]=2;
    for (i=3; i<=200; i++)
    {
        for (j=100; j>=0; j--)
        {
            a[i][j]+=a[i-1][j]+a[i-2][j];
            if (a[i][j]>=10)
            {
                a[i][j-1]+=a[i][j]/10;
                a[i][j]=a[i][j]%10;
            }
        }
    }
    cin>>n;
    while(n--)
    {
        char str[210];
        cin>>str;
        int l=strlen(str);
        int p;
        for (j=0; j<=100; j++)
            if (a[l][j]!=0)
                break;
        p=j;
        for (j=p; j<=100; j++)
            cout<<a[l][j];
        cout<<endl;
    }
    return 0;
}