1sting

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 4133    Accepted Submission(s): 1547

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

 

 

Author

z.jt

 

 

Source

 

 

Recommend

lcy   |   We have carefully selected several similar problems for you:            

//思路： 递推； 数中只存在1 和2 这两个数字 → → → f(n) = f(n-1) + f(n-1) ;

1 #include 
      
        2 #include 
       
         3 int fei[220][1001]; 4 int main() 5 { 6     int n; 7     char str[220]; 8     int i, j; 9     int temp, plus = 0;10     memset(fei, 0, sizeof(fei));11     fei[1][0] = 1;12     fei[2][0] = 2; 13     for(i=3; i<201; i++)  14     {15         for(j=0; j<1001; j++)     //二维数组下标表示数的位数；16         {17             temp = fei[i-1][j] + fei[i-2][j] + plus;18             fei[i][j] = temp%10;19             plus = temp/10;20         }21     }22     scanf("%d", &n);23     while(n--)24     {25         scanf("%s", str);26         int len = strlen(str);27         for(i=1000; i>=0; i--)28         if(fei[len][i])29         break;30         for(; i>=0; i--)31         printf("%d", fei[len][i]);32         printf("\n");33     }34     return 0;35 }