位数问题

【问题描述】
  在所有的N位数中，有多少个数当中有偶数个数字3？

由于结果可能很大，你只需要输出这个答案对12345取余的值。
【输入格式】
     读入一个数N
【输出格式】
     输出有多少个数中有偶数个数字3。
【输入样例】
     2
【输出样例】
    73
【数据规模】
    1<=N<=1000
【样例说明】
    在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个

算法分析：

方法一：排列组合(但需要运用动态规划)。

可以列出公式,在n个格子中放x个3(其中x为偶数,包括0)：

含义为在n个格子中取x个3,且不考虑第一位的特殊情况为

而第一位为0的情况是：

两者减下,就为答案。

算法二：递推

考虑这种题目,一般来说都是从第i-1位推导第i位,且当前位是取偶数还是取奇数的。
恍然大悟.可以用f[i][0]表示前i位取偶数个3有几种情况,f[i][1]表示前i位取奇数个3有几种情况。

则状态转移方程可以表示为:
f[i][0]=f[i-1][0]*9+f[i-1][1];
f[i][1]=f[i-1][0]+f[i-1][1]*9;
边界条件:f[1][1]=1;f[1][0]=9;

 1 【参考程序】
 2 #include<iostream>
 3 using namespace std;
 4 int main()
 5 {
 6   int f[1001][2],n,i,x;
 7   cin>>n;
 8   f[1][1]=1;f[1][0]=9;                        
 9   for(i=2;i<=n;i++) 
10    {   
11       x=f[1][0];
12       if(i==n)x--;
13       f[i][0]=(f[i-1][0]*x+f[i-1][1])%12345;
14       f[i][1]=(f[i-1][1]*x+f[i-1][0])%12345;   
15    }
16    cout<<f[n][0]; 
17    return 0;
18 }