TCHS 10 Championship Round Hard TheLuckyNumbersLevelThree

数論+DPでスーパー苦手な感じの。

問題

4または7で割り切れる数をラッキーな数とする。
a以上b以下の全てのラッキーな数を10進数で表したとき、各数字の出現回数を求めよ。

制約条件

a,b≦10^16

方針

n以下のラッキーな数の中の数字iの出現回数を求めることを考える。
これは以下のようなDPでできる。


dp[今までの長さ][今までに出現したiの回数][今までの数字がnより小さいか][先頭が0でないか][28で割った余り]
にそれぞれの数の総数を持たせてDP。

ソースコード

りんごさんの写経したので略。