P1002 位数问题

题解

可以发现，奇数个 \(3\) 一定由偶数个 \(3\) 推出。定义 \(f_1(i)\) 为 \(i\) 位数中有奇数个 \(3\) 的数的数量，\(f_2(i)\) 为 \(i\) 位数中有偶数个 \(3\) 的数的数量。

计算 \(f_1(i)\) 时，可以从 \(i - 1\) 位数中有奇数个 \(3\) 的所有数末尾添加一个不是 \(3\) 的一位数（这里包括 \(0\)）得到，或者从 \(i - 1\) 位数中有偶数个 \(3\) 的所有数末尾添加一个 \(3\) 来得到 \(i\) 位数中有奇数个 \(3\) 的所有数。\(f_2(i)\) 同理。则有

\[ f_1(i) = f_2(i - 1) + f_1(i - 1) * 9 \\ f_2(i) = f_1(i - 1) + f_2(i - 1) * 9 \]

\(0\) 不是一位数，所以 \(f_1(1) = 1, f_2(1) = 8\)。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int mod = 12345;

int n, f2[1005], f1[1005];

signed main(){
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    f2[1] = 8, f1[1] = 1;
    for(int i = 2; i <= n; i++){
        f2[i] = (f1[i - 1] + f2[i - 1] * 9) % mod;
        f1[i] = (f2[i - 1] + f1[i - 1] * 9) % mod;
    }
    cout << f2[n] % mod;

    return 0;
}