【题目描述】
在所有的NN位数中，有多少个数中有偶数个数字33?由于结果可能很大，你只需要输出这个答案对1234512345取余的值。
【输入】
读入一个数N(N≤1000)N(N≤1000)。
【输出】
输出有多少个数中有偶数个数字33。
【输入样例】
2
【输出样例】
73
递推思路
当 N=1，数字范围为 0 ~ 9，合计 9-0+1=10 个。
（1）含有偶数个 3 数字有 9 个（0、1、2、4、5、6、7、8、9）。
（2）含有奇数个 3 数字有 1 个（3）。
当 N=2，数字范围为 10 ~ 99，合计 99-10+1=90 个。
（1）含有偶数个 3 数字的构成：前面一位数中含有奇数个 3 数字，在其前面加上数字 3 的组合，有 1*1=1个，即数字 33，这样有 1 个数字；前面一位含有偶数个 3 数字（0、1、2、4、5、6、7、8、9），在其前面加上不是 3 的数字（1、2、4、5、6、7、8、9）的组合，有 8*9=72 个。合计 72+1=73。
（2）含有奇数个 3 数字的构成：前面一位数中含有奇数个 3 ，在其前面加上数字为（1、2、4、5、6、7、8、9）的组合，有 8*1=8 个。前面一位数中含有含有偶数个 3 数字（0、1、2、4、5、6、7、8、9），在其前面加上数字为 3 的组合，有 9*1=9 个。合计 8+9=17 个。
当 N=3，数字范围为 100 ~ 999，合计 999-100+1=900 个。
（1）含有偶数个 3 数字的构成：前面两位数字中含有奇数个 3（有 1*9+9*1 个，即18个，注意这个时候数字 0 可以放在前头，因为百位我们还能加数字），在其前面加上数字 3 的组合，合计 18*1=18 个；前面两位数字中含有偶数个 3（有 9*9+1*1 个，即82个，注意这个时候数字 0 可以放在前头，因为百位我们还能加数字） ，数字前加上不是 3 的数字（1、2、4、5、6、7、8、9），有 82*8=656。合计有 18+656=674 个。
（2）含有奇数个 3 数字的构成：前面两位数字中含有奇数个 3（有 1*9+9*1 个，即18个，注意这个时候数字 0 可以放在前头，因为百位我们还能加数字），在其前面加上不是 3 的数字（1、2、4、5、6、7、8、9）的组合，合计 18*8=144 个；前面两位数字中含有偶数个 3（有 9*9+1*1 个，即82个，注意这个时候数字 0 可以放在前头，因为百位我们还能加数字） ，数字前加上数字 3，有 82*1=82。合计有 144+82=226 个。
以此类推。这样我们就可以推倒出如下的递推公式：
N 表示位数，a[i] 表示到第 i 位包含偶数个 3 的数字数量，b[i] 表示到第 i 位包含奇数个 3 的数字数量
a[1] = 9 b[1] = 1
当 i<N 的时候
a[i] = a[i-1]*9 + b[i-1]*1 b[i] = a[i-1]*1 + b[i-1]*9
当 i==N 的时候，由于首位不能为零
a[i] = a[i-1]*8 + b[i-1]*1 b[i] = a[i-1]*1 + b[i-1]*8
代码搁这里呢
#include<bits/stdc++.h>
using namespace std;
const int Max=1e3+2;
unsigned long long a[Max];
unsigned long long b[Max];
int main()
{
int n;
cin>>n;
int k=9;
a[1]=9;
b[1]=1;
for(int i=2; i<=n; i++)
{
if(i==n) k=8;
a[i]=(a[i-1]*k+b[i-1])%12345;
b[i]=(a[i-1]+b[i-1]*k)%12345;
}
cout<<a[n];
return 0;
}此代码仅供参考，请勿纯抄