学步园

http://acm.hdu.edu.cn/showproblem.php?pid=3485

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int dp[10005][4];
int main()
{
    dp[2][0]=1;
    dp[2][1]=1;
    dp[2][2]=1;
    dp[2][3]=1;
    int i;
    dp[1][0]=0;
    dp[1][1]=0;
    dp[1][2]=1;
    dp[1][3]=1;
    for(i=3;i<=10000;i++)
    {
        dp[i][0]=(dp[i-1][0]+dp[i-1][3])%9997;
        dp[i][1]=(dp[i-1][0])%9997;
        dp[i][2]=(dp[i-1][2]+dp[i-1][1])%9997;
        dp[i][3]=(dp[i-1][2]+dp[i-1][1])%9997;
    }
    int n;
    while(scanf("%d",&n),n!=-1)
    {
        printf("%d\n",(dp[n][0]+dp[n][1]+dp[n][2]+dp[n][3])%9997);
    }
    return 0;
}