HDU 3485 Count 101 (전달)

C - Count 101
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit 
Status  
Practice  
HDU 3485
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
 
Sample Output
7 12
Hint

We 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 


    n                   0 1             

                        = =

#include<cstdio>

#include<iostream>

#include<bitset>

#include<algorithm>

using namespace std;

int a[10000+10];

int main()

{

    int n;

    int i,j;

    a[0]=1;

    a[1]=2;

    a[2]=4;

    a[3]=7;

    a[4]=12;

    for(i=5;i<=10000;i++)

    {

        a[i]=(a[i-1]+a[i-2]+a[i-4])%9997;

    }

    while(scanf("%d",&n)!=EOF)

    {

        if(n==-1) break;

        printf("%d
",a[n]);

    }

    return 0;

}