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。
ソースコード
りんごさんの写経したので略。