1312：【例3.4】昆虫繁殖

传送门：http://ybt.ssoier.cn:8088/problem_show.php?pid=1313

 

【题目描述】

在所有的N

位数中，有多少个数中有偶数个数字3?由于结果可能很大，你只需要输出这个答案对12345

取余的值。

【输入】

读入一个数N(N≤1000)

。

【输出】

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

。

【输入样例】

2

【输出样例】

73

#include<iostream>
using namespace std;
#define N 12345
int main()
{
    int n,f[1001][2];
//F【I】【0】表示前I位3的个数为偶数的个数
//F【I】【1】表示前I位3的个数为奇数的个数
   cin>>n;
   f[1][0]=9;
   f[1][1]=1;
    for(int i=2;i<=n;i++)
    {
        int x=f[1][0];
        if(i==n)x--;
        f[i][0]=x*f[i-1][0]+f[i-1][1];
        f[i][1]=x*f[i-1][1]+f[i-1][0];
        f[i][0]%=N;
        f[i][1]%=N;
    }
    cout<<f[n][0]<<endl;
}