nyoj655光棍的yy

光棍的yy

时间限制：1000 ms  |  内存限制：65535 KB 难度：2 描述

yy经常遇见一个奇怪的事情，每当他看时间的时候总会看见11:11，这个很纠结啊。

现在给你m个1，你可以把2个1组合成一个2，这样就不是光棍了，问这样的组合有多少种？？

例如（111  可以拆分为 111 12 21  有三种）

输入

第一行输入一个n表示有n个测试数据
以下n行，每行输入m个1
(1 <= n,m <= 200)

输出

输出这种组合种数，占一行

样例输入

3 11 111 11111

样例输出

2 3 8

思路：试了1，11，111，1111，11111，后发现是斐波那契数列，再看数据范围200个1，大数，OK。

几组测试数据：

1111111111111111111111111111111111111111111111111111
答案
53316291173

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
答案
573147844013817084101


11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
答案
453973694165307953197296969697410619233826

AC代码：

#include <stdio.h> #include <string.h> int main() {int n, i, j, c, b, L;char s[202][62], m[202];memset(s,0,sizeof(s));s[1][0] = 1;s[2][0] = 2;s[1][60] = 1;s[2][60] = 1;for(i = 3; i < 201; i++) {c = 0;L = s[i-1][60];for(j = 0; ; j++) {if(j >= L && c == 0) break;b = s[i-2][j] + s[i-1][j] + c;s[i][j] = b%10;c = b/10;}s[i][60] = j;}//freopen("input.txt","r",stdin);scanf("%d", &n);while(n--) {scanf("%s", m);int a = strlen(m);L = s[a][60]-1;for(i = L; i > -1; i--) {printf("%c", s[a][i]+48);}printf("\n");}//fclose(stdin);return 0; }

总结

以上是生活随笔为你收集整理的nyoj655光棍的yy的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。