HDU3485 &&CSU1363:Count 101

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?

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

7
12
HintWe 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
 

這道題我純粹是靠列出一些數字找規律的。。。

#include 
#include 
#include 
using namespace std;

const int mod = 9997;
int a[10005] = {0,2,4,7,12};

int main()
{
    int i;
    for(i = 5; i<=10000; i++)
        a[i] = (a[i-1]+a[i-2]+a[i-4])%mod;
    while(~scanf("%d",&i),i!=-1)
        printf("%d\n",a[i]);

    return 0;
}