题目描述
Once upon a time,there's a boy whose name is lili.He likes to create many wonderful things.One day, he happens to come to a beautiful garden.There he picks many pretty little stones.Again,his heart tells him that he should use them to create some incredible things!So he decides to put them in a line of boxes,each box has at most one stone,just as the road which he used to walk on in his childhood.But again,he wants to make his works different.So he wants no two adjacent boxes to have stones both.He wonders how many ways that stones be put into boxes.Can you help him to finish his great work?
输入格式
multiple cases：
n(0<=n<=100000) the number of the boxes
输出格式
The number described above MOD 10007.
输入样例
0
1输出样例
1
2热身赛的一道斐波那契水题, 感觉不会有人需要看这题的题解的XD
/*
USER_ID: test#birdstorm
PROBLEM: 178
SUBMISSION_TIME: 2014-03-08 11:30:54
*/
#include<stdio.h>
#include<stdlib.h>
#define For(i,m,n) for(i=m;i<n;i++)
#define MAXN 1000005
#define MOD 10007int dp[MAXN];void solve()
{int i;dp[0]=1; dp[1]=2;For(i,2,MAXN) dp[i]=(dp[i-1]+dp[i-2])%MOD;
}main()
{int n;solve();while(scanf("%d",&n)!=EOF) printf("%d\n",dp[n]);return 0;
}