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

2021/10/6 23:13:25

本文主要是介绍一本通 1313:【例3.5】位数问题 (递推/动态规划),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一本通 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位推导。

【我的答案】

# 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;
} 


这篇关于一本通 1313:【例3.5】位数问题 (递推/动态规划)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程