DPの解けない問題2問目

DPで解く問題だとわかっていても解けない。
たとえば以下の問題。

TopCoder SRM 771 Div1 Easy - AllEven

A以上B以下の整数のうち、0 ~ 9の各数字の出現回数が偶数である整数はいくつあるか、を求める問題。制約は0 <= A, B <= 10^18 - 1。

既にDPで解くことはわかっているんだけど、どうDPを定義しても遷移が複雑になる。そして、頭の中がオーバーフローする。

一度寝て起きたらまた考えられるようになるかな。