2014/3/9 长沙多校（第二次）

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 #include <cmath>
 5 #define maxn 10005
 6 
 7 using namespace std;
 8 
 9 int n;
10 int dp[maxn][2];
11 
12 void init()
13 {
14     dp[0][0]=0;dp[0][1]=0;
15     dp[1][0]=1;dp[1][1]=1;
16     dp[2][0]=2;dp[2][1]=2;
17     for(int i=3;i<maxn;i++)
18     {
19         dp[i][0]=dp[i-1][1]+dp[i-1][0];
20         dp[i][0]%=9997;
21         dp[i][1]=dp[i-1][1]+dp[i-2][0];
22         dp[i][1]%=9997;
23     }
24     return;
25 }
26 int main()
27 {
28     init();
29     while(cin>>n && n>=0)
30     {
31         printf("%d\n",(dp[n][0]+dp[n][1])%9997);
32     }
33     return 0;
34 }