0
已解决
新手守护
题目链接： 酷町堂：4970
4970 喵尔基里
时间限制：1000毫秒
内存限制：128MB
题目描述 De**ion
芬里尔喵在结束了奥丁的邪恶之后。打算组建自己的喵武神军队，喵尔基里们。芬里尔**武神不计其数，给他们从1开始依次往后编号。喵尔基里需要选择一批武神队长。芬里尔喵打算选择出编号中含有偶数个5的武神作为队长，请问这样的队长能有多少个。
输入描述 Input De**ion
一行，一个整数n，表示武神的最多编号有n位
输出描述 Output De**ion
一个整数，表示队长的数量，输出最后的答案对100007的求余后的结果
样例输入 Sample Input
5
样例输出 Sample Output
66383
数据范围及提示 Data Size & Hint
n<=20
1
已采纳
高级光能
找规律啊！
两个函数：
int f2(int n){ if(n==1) return 1; return (f2(n-1)*9+f1(n-1))%100007; }
int f1(int n){ if(n==1) return 8; return (f1(n-1)*9+f2(n-1))%100007; }
但是需要在main函数下面声明
