题目描述
请编程求出所有的n位数中，有多少个数中有偶数个数字3。

输入
一个整数n，0<n<1000。

输出
一个整数，表示n位数中有多少个数有偶数个3。（由于答案可能很大，你需要输出ans mod 10007后的结果）

样例输入 复制
2
样例输出 复制
73

要用递推写，下面29分

#include<bits/stdc++.h>
using namespace std;
long long n,f[2][1005],ans;
int main(){
	cin>>n;
	f[0][1]=9;
	f[1][1]=1;
	f[0][2]=73;
	f[1][2]=17;
	for(int i=3;i<=n;i++)
	{
		f[0][i]=(8*f[0][i-1]+f[1][i-1])%10007;
		ans=(9*(int)pow(10,i))%10007;
		f[1][i]=(ans-f[0][i])%10007; 
	}
	cout<<f[0][n];
    return 0;
} 

f[0][i]就是i位数有多少个偶数个3，f[1][i]就是i位数有多少个奇数个3，思路是最高位除了0的八个数偶数个3都能放，然后后面n-1位也要放偶数个3，最高位还能放1个奇数个3，然后后面n-1位也要放奇数个3，所以加起来等于f[0][i]=(8*f[0][i-1]+f[1][i-1])%10007;然后后面总数－偶数等于奇数，用pow会炸，还有什么方法吗