信息学一本通 1313：【例3.5】位数问题

【题目描述】

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

【输入】

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

【输出】

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

【输入样例】

2

【输出样例】

73

链接：https://pan.baidu.com/s/1gOOOlCqxtPxgusGKya55Ag?pwd=05d3

#include <cstdio>
#include <iostream>
using namespace std;

int main() {
	int n, x, f[1001][2];
	cin >> n;

	if (n <= 1) {
		cout << 9 << endl;			// 一位数字，可以取除了3之外的0-9中任意一个，即0个3 
	} else {
		f[1][0] = 8;				// 大于等于2位数字，最高位不能为0。所以f[1][0]前1位取偶数个3，只能从0-9中取除了0和3之外的8个数字 
		f[1][1] = 1;				// f[1][1]前1位取奇数个3，只能取3一个数字 
		for (int i=2; i<=n; i++) {
			f[i][0] = (f[i-1][0]*9 + f[i-1][1]*1) % 12345;
			f[i][1] = (f[i-1][1]*9 + f[i-1][0]*1) % 12345;
		} 
	
		cout << f[n][0] << endl;
	}	
	
	return 0;
}