一本通-1313：【例3.5】位数问题（动态规划）

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

【输入】 输入包含一行，一个字符串，长度不超过1000。读入一个数N。

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

【输入样例】 2

【输出样例】 73

---

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

const int MODE = 12345;

vector<int> odd(1005); //奇数
vector<int> even(1005); //偶数

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; cin >> n;
    odd[1] = 1; even[1] = 9;
    for (int i = 2; i <= n; ++i) {
        int tmp = 9;
        if (i == n) --tmp;
        odd[i] = (even[i - 1] + odd[i - 1] * tmp) % MODE;
        even[i] = (odd[i - 1] + even[i - 1] * tmp) % MODE;
    }
    cout << even[n] << endl;

    return 0;
}

用odd[i]代表从个位起的i位存在奇数个3的数的个数，even代表从个位起的i位存在偶数个3的数的个数。

值得注意的就是最高位不能为0，所以在计算最高位时候的可能性变成了8.