【題目描述】

在所有的N位數中，有多少個數中有偶數個數字3?由于結果可能很大，你只需要輸出這個答案對12345取余的值。

【輸入】

讀入一個數N(N≤1000)。

【輸出】

輸出有多少個數中有偶數個數字3。

【輸入樣例】

2

【輸出樣例】

73

【題解代碼】

#include<bits/stdc++.h>
using namespace std;/* 1位數時               2位數時                         3位數時
奇數個3的個數    odd[1]=1     odd[2]=9*odd[1]+1*even[1]      odd[2]=9*odd[1]+1*even[1]
偶數個3的個數    even[1]=9    even[2]=1*odd[1]+9*even[1]     even[2]=1*odd[1]+9*even[1]
*//*
邊界條件：odd[1]=1  even[1]=9遞推關系式：odd[i] = 9 * odd[i - 1] + 1 * even[i - 1];even[i] = 1 * odd[i - 1] + 9 * even[i - 1];注意：最高位不能為0（即i=n時）
*/const int N = 1e3 + 10;
int odd[N], even[N];int main()
{int n; cin >> n;odd[1] = 1, even[1] = 9;for (int i = 2; i <= n; i++){if (i == n)  //最高位不能為0{odd[i] = (8 * odd[i - 1] + 1 * even[i - 1]) % 12345;even[i] = (1 * odd[i - 1] + 8 * even[i - 1]) % 12345;}else{odd[i] = (9 * odd[i - 1] + 1 * even[i - 1]) % 12345;even[i] = (1 * odd[i - 1] + 9 * even[i - 1]) % 12345;}}cout << even[n];return 0;
}