1313：【例3.5】位数问题（递推）

【题目描述】
在所有的N位数中，有多少个数中有偶数个数字3?由于结果可能很大，你只需要输出这个答案对12345取余的值。

【输入】
读入一个数N(N≤1000)。

【输出】
输出有多少个数中有偶数个数字3。

【输入样例】
2
【输出样例】
73

#include 
using namespace std;
int a[1005][2];
int main() {
	int n;
	cin>>n;
	if(n<=1) {//只有一位，只有一个数：3，为奇数个3,故直接返回10-1 
		cout<<9;
	} else {//最高位不能为0 
        //只有第一位只有9个数，其为最高位，后面的都可以取0~9;
		a[1][0]=8;//9-1  只能从0-9中取除了0和3之外的8个数字 
		a[1][1]=1; a[1][1]前1位取奇数个3，只能取3一个数字
		for(int i=2; i<=n; i++) {
			a[i][0]=(a[i-1][0]*9+a[i-1][1]*1)%12345;
			a[i][1]=(a[i-1][0]*1+a[i-1][1]*9)%12345;
		}
		cout<