1313：【例3.5】位数问题

http://ybt.ssoier.cn:8088/problem_show.php?pid=1313

从低位往高位递推

#include<iostream>
using namespace std;
const int maxn=1000+5;
int f[maxn][2];

//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
//最高位不能为0，特殊处理
int main()
{
     int n;
     cin>>n;
     f[1][0]=9; f[1][1]=1;
     int i;
     int k=9;
     for(i=2;i<=n;i++)
     {
         //最高位不能为0
         if(i==n)
             k=8;
         f[i][0]=(f[i-1][0]*k + f[i-1][1])%12345;
         f[i][1]=(f[i-1][0] + f[i-1][1]*k)%12345;
     }
     if(n==1)
         f[1][0]=8;   
     cout<<f[n][0];
     return 0;
}