在所有的N位数中，有多少个数中有偶数个数字3（说明，0是偶数）？ 【输入格式】 读入一个数N 【输出格式】 输出有多少个数中有偶数个数字3。 【输入样例】 2 【输出样例】 73(由于 位数 比较大的情况下,导致输出数据可能越界,因此,输出个数 % 12345 的结果) 【数据规模】 1<=N<=1000 (a+b)%c==(a%c+b%c)%c ==(a%c+b)%c 分析 任何位的数中，根据3的个数不同，分为两类 或者偶数位的3，或者包含 奇数位的3 1位数中(共10个数) 0，1，2，3，4，5，6，7，8，9， 包含0个3的数有 9个 包含1个3的数有1个 2位数中（90个 10~99） 包含偶数个3的数有 0个3+2个=89+11=72 包含奇数个3的数有 1个3= 9*1
【样例说明】 在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个
【算法分析】 前i位有偶数个3，必须满足以下条件： 前i-1位有偶数个3, 则 第i位不能取3 前i-1位有奇数个3，则第i位必须取3 可以用f[i][0]表示前i位取偶数个3有几种情况, f[i][1]表示前i位取奇数个3有几种情况。 则递推公式可以表示为: f[i][0] =f[i-1][0]*9+f[i-1][1]; (9：除3 外的每一个数字) f[i][1] =f[i-1][0] + f[i-1][1]*9; (9：除3 外的每一个数字) 边界条件: f[1][1]=1;f[1][0]=9; 说明：如果i 是最高位， 由于最高位不能是数字0 ，则将9改为8
#include<iostream> using namespace std; int main(){ int f[1001][2],n,i,x=9; cin>>n; f[1][1]=1;f[1][0]=9; for(i=2;i<=n;i++) { if(i==n) // i是最高位 x--; f[i][0]=(f[i-1][0]*x+f[i-1][1])%12345; f[i][1]=(f[i-1][1]*x+f[i-1][0])%12345; } cout<<f[n][0]; return 0; }