信息学奥赛一本通T1313-位数问题-题解（C++代码）思路提示

解题思路:

注意事项:

参考代码:

/*
even[i]：表示i位数中偶数个3的个数
odd[i]：表示i位数中奇数个3的个数
1、末位为3的情况：
	even[i] = odd[i - 1]
	odd[i] = even[i - 1]
2、末位非3的情况
	even[i] = even[i - 1] * 9;
	odd[i] = odd[i - 1] * 9;
综上：
	even[i] = even[i - 1] * 9 + odd[i - 1]
	odd[i] = odd[i - 1] * 9 + even[i - 1]
*/


#include <iostream>
using namespace std;
const int Mod = 12345;

int n;
int even[1005], odd[1005];

int main() {
	cin >> n;
	even[1] = 8, odd[1] = 1;
	for (int i = 2; i <= n; ++i) {
		even[i] = (even[i - 1] * 9 + odd[i - 1]) % Mod;
		odd[i] = (odd[i - 1] * 9 + even[i - 1]) % Mod;
	}
	cout << even[n] << endl;
	return 0;
}