Hust oj 1986 大悲咒（递推）

“南无（皈依）喝罗怛那哆罗夜耶（三宝）南无（皈依）阿唎耶（圣），婆卢羯帝（观）烁钵罗耶（自在）．菩提萨埵婆耶（觉有情）．摩诃萨埵婆耶（大觉有情）．摩诃迦卢尼迦耶（有大悲者）．唵（皈命），萨皤罗罚曳（一切尊）．数怛那怛写（为救济於一切恐怖者）．南无（皈命）悉吉栗埵（於彼）伊蒙阿唎耶（我圣）．婆卢吉帝室佛罗愣驮婆（观自在香山）．南无（皈命）那罗谨墀（言圣观自在贤爱．慈悲之心）．醯利摩诃皤哆沙咩（我今宣说）．萨婆阿他豆输朋（一切希望圆满而有光辉者）．阿逝孕（无比）．萨婆萨哆（一切鬼神不能打胜者）那摩婆萨哆，那摩婆伽（童真）．摩罚特豆（有道即令迷界清挣者）．怛侄他（谓）．唵（皈命）．阿婆卢醯（有光明智慧者）．卢迦帝（观自在）．迦罗帝（超越世间者）．夷醯唎（吁狮子王）．摩诃菩提萨埵（大菩萨）．萨婆萨婆（一切一切）．摩罗摩罗（忆念忆念），摩醯摩醯唎驮孕（心真言）．俱卢俱卢羯蒙（作作事业）．度卢度卢（保持保持）罚闍耶帝（游空者）．摩诃罚闍耶帝（大游空者）．陀罗陀罗（保持）．...”（看不懂你就别看了）

明天就是六级考试了，平时上课刷微博，下课看电视剧的阿B同学略微心急如焚，所以她决定临时抱佛脚。她在佛像面前趴了一天，念了1000遍上面这段大悲咒。佛祖被感动了，瞬时出现在她的面前。

 “我可以帮你实现一个愿望，请说吧。”

 “我想。。。我想。。”

 “说吧，不就是过六级这种事情么？”

 “有3*n的方格内放满1*3的相同骨牌，请问有几种情况呢？”

 “这个，这个。。。容我回去想想。”

有多组输入数据，对于每组数据只有一个输入n（1 ≤ n ≤ 100000）。

对于每组输出一个整数，表示骨牌的方案数，并且模100007。

1
2
3

1
1
2

最初看样例以为是斐波那契数，后来画着画着感觉不对。。。应该是f[I] = f[I-1]+f[I-3]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
#define maxn 100000
const int mod = 100007;
long long int f[maxn+10];
int main()
{int n;int i,j;f[1]=1;f[2]=1;f[3]=2;f[4]=3;for(i=5;i<=maxn;i++){f[i]=(f[i-1]%mod+f[i-3]%mod)%mod;}while(scanf("%d",&n)!=EOF){printf("%lld\n",f[n]);}
}