问题 D: 小“光棍节”

问题 D: 小“光棍节”

时间限制: 1 Sec  内存限制: 128 MB
提交: 561  解决: 125
[状态] [讨论版] [提交] [命题人:]
题目描述
今天是11月1日,跟11月11日只差一个1,也算是个小“光棍节”吧。这么有意义的节日值得做一道题来庆祝一下。 
给一个整数n,代表一个字符串的总长度, 这个字符串只有0和1构成。 然而,在11月1日这样一个“单身狗”需要反省的日子里,我们不想见到更多的1了。于是,我们要求字符串内不允许有等于或大于3个1连在一起的情况。那么现在问题来了,这个长度为n的0-1字符串总共会有多少种?
例如n为2时,有如下4种:
01
10
11
00 
输入
一个整数T ,代表有T 组测试数据, 然后每组测试输入一个整数n(n<=50), 代表字符串的长度
输出
输出长度为n的0-1字符串有多少种
样例输入 Copy
3
0
1
2
样例输出 Copy
0
2
4
提示
计算结果有可能溢出