$\mathrm{smaller} \to \mathrm{next\_smaller}$
- $\mathrm{smaller} = 1 \implies \mathrm{next\_smaller} = 1$
- $(\mathrm{smaller} = 0) \land (d < N_i) \implies \mathrm{next\_smaller} = 1$
- $(\mathrm{smaller} = 0) \land (d = N_i) \implies \mathrm{next\_smaller} = 0$
$\mathrm{leading} \to \mathrm{next\_leading}$
- $\mathrm{next\_leading} = \begin{cases} 1 & (\mathrm{leading} = 1) \land (d = 0) \\ 0 & \text{otherwise} \end{cases}$
$\mathrm{mod} \to \mathrm{next\_mod}$
- $\mathrm{next\_mod} = (\mathrm{mod} + d) \bmod 3$
$\mathrm{has3} \to \mathrm{next\_has3}$
- $\mathrm{next\_has3} = \begin{cases} 1 & (d = 3) \\ \mathrm{has3} & \text{otherwise} \end{cases}$
$\mathrm{bit} \to \mathrm{next\_bit}$
- $\mathrm{next\_bit} = \mathrm{bit} \: \mathrm{OR} \: 2^d$

ここで、 $\mathrm{leading} = 1$ の間は $\mathrm{bit}$ を更新しないことに注意。

※ 実際は $\mathrm{mod}$ や $\mathrm{has3}$ の値も更新されないが、 $d = 0$ の場合はどちらの更新にも影響を及ぼさないので、特別な場合分けは必要ない。

$N$ の桁数を $l$ として、 $l$ 桁目までの更新が終わったら、 $\mathrm{dp}[l][\mathrm{smaller}][0][\mathrm{mod}][\mathrm{has3}][\mathrm{bit}]$ の各状態について、以下の条件のうちちょうど一つだけを満たす場合に限り、答えにその状態の値を加算する。

$\mathrm{mod} = 0$
$\mathrm{has3} = 1$
$\mathrm{popcount}(\mathrm{bit}) = 3$

答えは $998244353$ で割った余りを出力することに注意。

このDPテーブルの状態数は $2 \times 2 \times 3 \times 2 \times 2^{10} = 24576$ であり、各状態からの遷移は最大で $10$ 通りなので、時間計算量は $O(l \times 12288 \times 10) = O(l)$ 。また、空間計算量については、今回はDPの遷移が直前の状態からしか起こらないため、 Next DPの要領で、現在の状態と次の状態の2つのテーブルだけを保持すればよく、空間計算量は $O(1)$ と見なせる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#if __has_include(<atcoder/all>)
5.#include <atcoder/all>
6.using namespace atcoder;
7.#endif
8. 
9.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
10. 
11.using mint = modint998244353;
12. 
13.// ======================================== //
14. 
15.int main()
16.{
17.    string N;
18.    cin >> N;
19. 
20.    int l = N.size();
21. 
22.    vector<vector<vector<vector<vector<mint>>>>> dp(2, vector<vector<vector<vector<mint>>>>(2, vector<vector<vector<mint>>>(3, vector<vector<mint>>(2, vector<mint>((1 << 10), 0)))));
23.    dp[0][1][0][0][0] = 1;
24. 
25.    rep(i, 0, l) {
26.        vector<vector<vector<vector<vector<mint>>>>> ndp(2, vector<vector<vector<vector<mint>>>>(2, vector<vector<vector<mint>>>(3, vector<vector<mint>>(2, vector<mint>((1 << 10), 0)))));
27.        int limit = N[i] - '0';
28. 
29.        rep(smaller, 0, 2) {
30.            rep(leading, 0, 2) {
31.                rep(mod, 0, 3) {
32.                    rep(has3, 0, 2) {
33.                        rep(bit, 0, (1 << 10)) {
34.                            mint now = dp[smaller][leading][mod][has3][bit];
35.                            if (now.val() == 0) continue;
36. 
37.                            int upper = 9;
38.                            if (!smaller) upper = limit;
39. 
40.                            rep(d, 0, upper + 1) {
41.                                int next_smaller = smaller;
42.                                if (!smaller && d < limit) {
43.                                    next_smaller = 1;
44.                                }
45. 
46.                                int next_leading = (leading && d == 0);
47. 
48.                                int next_mod = (mod + d) % 3;
49.                                int next_has3 = has3;
50.                                int next_bit = bit;
51. 
52.                                if (!next_leading) {
53.                                    next_bit |= (1 << d);
54.                                    if (d == 3) {
55.                                        next_has3 = 1;
56.                                    }
57.                                }
58. 
59.                                ndp[next_smaller][next_leading][next_mod][next_has3][next_bit] += now;
60.                            }
61.                        }
62.                    }
63.                }
64.            }
65.        }
66. 
67.        dp = move(ndp);
68.    }
69. 
70.    mint ans = 0;
71.    rep(smaller, 0, 2) {
72.        int leading = 0;
73. 
74.        rep(mod, 0, 3) {
75.            rep(has3, 0, 2) {
76.                rep(bit, 0, (1 << 10)) {
77.                    mint now = dp[smaller][leading][mod][has3][bit];
78.                    if (now.val() == 0) continue;
79. 
80.                    int cnt = 0;
81.                    if (mod == 0) cnt++;
82.                    if (has3) cnt++;
83.                    if (__builtin_popcount(bit) == 3) cnt++;
84. 
85.                    if (cnt == 1) {
86.                        ans += now;
87.                    }
88.                }
89.            }
90.        }
91.    }
92. 
93.    cout << ans.val() << endl;
94. 
95.    return 0;
96.}