この問題の制約下では f(x,B) の最大値は f(1015−1,1015)=f(999999999999999,1000000000000000)=136 であり、大体は f(x,B) の方が答えに寄与します。これに注目して、
- dpi,small=(i 桁目まで見て A 以下となることが確定して[いる・いない]状態の通り数とそのようなもの全てに対する f の値の総和) とした桁DPを用いて ans:=x=0∑Af(x,B) を求める
- ∣x−B∣ が寄与しうる x(B−136 から B+136 までの高々 273 通り)について愚直に寄与を求めて ans を修正する
といった処理を行うとこの問題が解けます。