一本通 1313:【例3.5】位数问题 (递推/动态规划)

一本通 1313:【例3.5】位数问题

目录

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 15814 通过数: 8606

【题目描述】

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

【输入】

读入一个数N(N≤1000)。

【输出】

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

【输入样例】

2

【输出样例】

73

【相关知识】

特别注意,零是特殊的偶数!

要计算在N位数中,含有奇数个(或偶数个)数字3(或者1-9之间的任何数字)的数的个数,可以逐个由第1位推导。

一本通 1313:【例3.5】位数问题 (递推/动态规划)

【我的答案】

# 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;
} 
上一篇:文件的散列与校验:.NET发现之旅(五)


下一篇:KVM下的桥接网卡配置