Count 101
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 400 Accepted Submission(s): 219
Problem Description
You know YaoYao is fond of his chains. He has a lot of chains and each chain has n diamonds on it. There are two kinds of diamonds, labeled 0 and 1. We can write down the label of diamonds on a chain. So each chain can be written as a sequence consisting of 0 and 1.
We know that chains are different with each other. And their length is exactly n. And what’s more, each chain sequence doesn’t contain “101” as a substring.
Could you tell how many chains will YaoYao have at most?
We know that chains are different with each other. And their length is exactly n. And what’s more, each chain sequence doesn’t contain “101” as a substring.
Could you tell how many chains will YaoYao have at most?
Input
There will be multiple test cases in a test data. For each test case, there is only one number n(n<10000). The end of the input is indicated by a -1, which should not be processed as a case.
Output
For each test case, only one line with a number indicating the total number of chains YaoYao can have at most of length n. The answer should be print after module 9997.
Sample Input
3 4 -1
Sample Output
7 12HintWe can see when the length equals to 4. We can have those chains: 0000,0001,0010,0011 0100,0110,0111,1000 1001,1100,1110,1111
Source
Recommend
zhengfeng
状态：
d[i][j][k]表示前i个数第i-1个是j第i-2个是k的满足条件的串的个数
状态转移方程：
d[i][k][0]=(d[i][k][0]+d[i-1][j][k])%9997
d[i][k][1]=(d[i][k][1]+d[i-1][j][k])%9997 (jk!='10')
d[i][k][1]=(d[i][k][1]+d[i-1][j][k])%9997 (jk!='10')
边界：
d[1][0][0]=d[1][0][1]=1
d[2][j][k]=1
代码：