> 文档中心 > 信息学奥赛一本通1313:【例3.5】位数问题

信息学奥赛一本通1313:【例3.5】位数问题

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

【输入】
读入一个数N(N≤1000)。

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

【输入样例】

2

【输出样例】

73

code

#includeusing namespace std;long long a[1005];long long b[1005];int main(){    int n;    a[1]=1;    b[1]=8;    cin>>n;    for(int i=2;i<=n;++i)    {    a[i]=(a[i-1]*9+b[i-1])%12345;    b[i]=(b[i-1]*9+a[i-1])%12345;}    cout<<b[n];    return 0;}

![在这里插入图片描述](https://img-blog.csdnimg.cn/db290cbfb22343319791b8740c639a36.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA4Ly66YeR6b6Z4LyS5Yek5Yew4Ly7,size_20,color_FFFFFF,t_70

天天赞天天看!!!

我们明天再见,拜拜!