信息学奥赛一本通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;}