概要
- 公式解説の計算量：$O(|S|2^dd)$
- この記事の解説の計算量：$O(|S|d)$
解法
例えば $4$ 桁かつ 4567 未満の整数全体は，次のように分類できます．
- $1000$ の位ではじめて 4567 より小さくなるもの：1***, 2***, 3***
- $100$ の位ではじめて 4567 より小さくなるもの：40**, 41**, 42**, 43**, 44**
- $10$ の位ではじめて 4567 より小さくなるもの：450*, 451*, 452*, 453*, 454*, 455*
- $1$ の位ではじめて 4567 より小さくなるもの：4560, $\ldots$, 4566.
すると，$N$ 以下の整数を，$O(|S|d)$ 種に分類できます．各類は，「prefix が決まっていて，suffix 何文字かが自由に選べる」というタイプのものです．
leading zero を補完しても影響しない問題では，$3$ 桁以下の整数は 0*** として考慮できます．本問のように leading zero が影響する場合には 1**, 2**, $\ldots$, 9** 等を追加すればよいです．これで $N$ 未満の整数が分類できますが，$N$ 以下の整数を計算対象としたい場合は事前に $N$ をインクリメントしておくか，最後に $N$ 自身を追加すればよいです．
結局，次の形の問題が $O(|S|d)$ 個解ければよいことになります：
- $n$ 個のワイルドカード $***\cdots$ をそれぞれ $0,1,\ldots,9$ に置換する方法であって，特定の $k$ 個の文字が奇数回，それ以外が偶数回現れるようなものを数えよ．
そこで，次を前計算することにします：
- $\mathrm{dp}[n][k]$：$0, 1, \ldots, 9$ からなる長さ $n$ の列で，ちょうど奇数回出現する文字が $k$ 種類であるものの個数
$\mathrm{dp}[n][k]$ は簡単な dp で計算できます．対称性の扱いには注意してください．私の上述の定義では，例えば「奇数回出現する文字の集合が ${1, 2, 5, 7}$ であるような長さ $n$ の列」の個数は $\mathrm{dp}[n][4]$ を $\binom{10}{4}$ で割ったものとなります．
このような前計算は，$O(|S|d)$ 時間で行えます．この前計算のもと，各 prefix に対して条件を満たす suffix の取り方が取得できて，本問題は $O(|S|d)$ 時間で解くことができます．
このように整数区間を prefix + (wildcards) の形の区間に分解して，wildcards 部分を上手く扱うことで，桁 dp が高速化できる問題はときどきあります．
