E. 数 TDPC_桁DP - 競技プログラミングのべんきょうきろく

典型DP（動的計画法）コンテスト

典型とは書いてるけれども、正直なところ普通に、というより、ゲロ吐きそうなくらい難しい

これのE問題ときました^o^（日曜も終わった）
問題文
E: 数 - Typical DP Contest | AtCoder

この問題については、桁DPを使う。桁DPについては多分下のURLが詳しい
桁DP - CCS Wiki

僕のかいたこおど
Submission #447917 - Typical DP Contest | AtCoder

方針
nを文字列でキープ。　10000桁とか整数型こわれる
dpテーブル[0からn桁の最大(n = 2 なら99)までの個数][]

dp[1][0] なら 0~9までのDの倍数
dp[5][1] なら　0~99999まででDで割るとあまりが1の数

これを桁DPで求めていく。

N = 320008 を考えると
上のDPテーブルを元にすると
0~99999　のテーブルで下の3つが求められる
0~99999
100000 ~ 199999
200000 ~ 299999

途中で1や2の分だけdpの参照先をずらす

このとき、頭のsum = 3 % Dを持っておく。
頭の総和を持っておくことで、次のテーブルでの参照先のずらしに使う。

0~9999　のテーブルで略
300000 ~ 309999
310000 319999

上の条件で全部の組み合わせを数えておけば、0~319999までの数がもれることなく数え上げできる
このとき sum = (3+2)% D になっているので、
5 + 0, 5 + 1,..., 5 + 8 の各パターンがDで割り切れるか試して、最後の桁まで数え上げる

最後に 0　が含まれちゃってるのでこれは-1する。　おわり

ACした感想
133msで通ってるので、素直に答えの数え上げもテーブル化して再シミュレートしたほうが早かったのは反省。O(log_10(N)D^2 = 10^8)だから細かな高速化をしないと間に合わないのかなーと・・・
数時間かかったけど（途中で心折れたりした）、大会のランキングを見ると10分程度でできてる人がいるんだけどこれは何なのか。