ステップ 1 : 動的計画法の利用

まず、全体の通り数は以下のように求めることができます。

• $B$ 以下の場合に条件を満たす通り数 - $A$ 未満の場合に条件を満たす通り数

この問題では、非常に大きな数字が入力として与えられるため、int 型などの整数型に値を正確に格納することができません。

ここで、与えられた数字を文字列として扱い、次のような動的計画法を考えてみます。

$dp[i][j][S][k] :$ $i$ 桁目までで、状態が $j$ で、現れた数字の集合が $S$ で、各桁の数字の総和が $k$ であるような通り数

状態 $j = 1$ の場合は与えられた数字と同じ場合、$j = 0$ の場合は与えられた数字より小さい場合を表します。

この動的計画法により答えを求めることができますが、今回の制約の場合だと MLE になってしまう可能性があります。

ステップ 2 : 包除原理の利用

条件 $1$ と 条件 $2$ の二つの条件のいずれかを満たす通り数は、以下のように計算できます。

• 条件 $1$ を満たす通り数 $+$ 条件 $2$ を満たす通り数 $-$ 条件 $1$ と $2$ を満たす通り数

これを利用することによって、$B$ 以下の場合に条件を満たす通り数 と $A$ 以下の場合に条件を満たす通り数 をそれぞれ高速に求めることができます。

Python で実装する場合には、多次元配列の処理速度があまり高速でないことから $1$ 次元配列に直して実装することを推奨します。