位数问题(dp 递推）

位数问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 35  解决: 19
[提交][状态][讨论版][命题人:quanxing]

题目描述

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

输入

读入一个数N。

输出

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

样例输入

2

样例输出

73

提示

#include<cstdio>  
using namespace std;  
int main()  
{  
    int n,f[1001][2],i,x;  
    scanf("%d",&n);  
    f[1][1]=1;f[1][0]=9;  
    for(i=2;i<=n;i++)  
    {  
        x=f[1][0];  
        if(i==n) x--;  
        f[i][0]=(f[i-1][0]*x+f[i-1][1])%12345;  
// 增加一位，放入一个 3，就有上一位放入奇数个 3 的可能，  
//不放入 3 就等于上一位放入偶数个 3 再乘 0-9（除了3）；   
        f[i][1]=(f[i-1][1]*x+f[i-1][0])%12345;//同理  
    }  
    printf("%d
",f[n][0]);  
    return 0;  
}