hdu1865

1sting

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2444    Accepted Submission(s): 979

Problem Description

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.

 

Input

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.

 

Output

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

 

Sample Input

3

1

11

11111

 

Sample Output

1

2

8

 

#include<stdio.h>
#include<string.h>
int f[201][100];
int main()
{
char a[201];
int i,j,t,l,n;
f[0][1]=1;
f[1][1]=1;
for(i=2; i<=200; i++)
{
for(j=1; j<=40; j++)
f[i][j]=f[i-1][j]+f[i-2][j];
for(j=1; j<=40; j++)
{
if(f[i][j]>100000000)
{
f[i][j+1]+=f[i][j]/100000000;
f[i][j]%=100000000;
}
}
}
scanf("%d",&t);
getchar();
while(t--)
{
gets(a);
l=strlen(a);
for(i=40;;i--)
if(f[l][i]!=0)
break;
printf("%d",f[l][i]);
for(i--; i>=1; i--)
printf("%08d",f[l][i]);
printf(" ");
}
return 0;
}