一本通 1313:【例3.5】位数问题
目录时间限制: 1000 ms 内存限制: 65536 KB
提交数: 15814 通过数: 8606
【题目描述】
在所有的N位数中,有多少个数中有偶数个数字3?由于结果可能很大,你只需要输出这个答案对12345取余的值。
【输入】
读入一个数N(N≤1000)。
【输出】
输出有多少个数中有偶数个数字3。
【输入样例】
2
【输出样例】
73
【相关知识】
特别注意,零是特殊的偶数!
要计算在N位数中,含有奇数个(或偶数个)数字3(或者1-9之间的任何数字)的数的个数,可以逐个由第1位推导。
【我的答案】
# include <bits/stdc++.h>
using namespace std;
const int MAXLEN = 1003;
int odd[MAXLEN], even[MAXLEN];
int n;
int k = 9;
int main (){
cin >> n;
odd[1] = 1;
even[1] = 9;
for(int i = 2; i <= n; i++){
if(i == n){
k = 8;
}
odd[i] = (odd[i-1] * k + even[i-1])%12345;
even[i] = (even[i-1] * k + odd[i-1])%12345;
}
cout<<even[n];
return 0;
}