EDPC S - Digit Sum

桁和

考え方

ABCでいうと、E問題級。

いわゆる桁 DP。

free[i][r] を、i 桁目より後ろを自由に決めたとき、桁和を $D$ で割った余りが r になる個数とする。
これは、下の桁から順に作れる。

その事前処理をしておいて、上から順に桁を見ていく。
今見ている桁で $K$ の同じ桁より小さい値を置いた瞬間、それより後ろの桁は自由になる。
その自由になった後ろの桁の個数を、先に作った free から取り出せばよい。

具体的には、後ろの桁で必要な余りは $-(s + j) \bmod D$ になる。
ただし、$s$ は今見ている桁より上の桁和、$j$ は今の桁に置く値である。
これに対応する free[i][...] を答えに足していけば、$0$ 以上 $K$ 未満のパターン数になる。

問題は $1$ 以上 $K$ 以下なので、その分の補正を考える。
未満と以下の補正は、最初に $K$ に $1$ を足しておけばよい。
$0$ 以上と $1$ 以上の補正は、$0$ が必ず条件を満たすことから、単純に $-1$ しておけばよい。

計算量は $O(|K|D)$。

入力を受け取る。

k: 30
d: 4

$1$ 以上 $30$ 以下を数える代わりに、$0$ 以上 $31$ 未満を数えてから $0$ の分を引く。

まず、下 $1$ 桁を自由に決める場合を考える。
$0$ から $9$ までについて、$4$ で割った余りごとの個数は次のようになる。

余り	$0$	$1$	$2$	$3$
個数	$3$	$3$	$2$	$2$

$31$ 未満なので、十の位が $3$ より小さい場合を考える。

十の位が $0$ のとき、一の位の余りは $0$ であればよい。
該当する一の位は $0,4,8$ の $3$ 通りである。

十の位が $1$ のとき、一の位の余りは $3$ であればよい。
該当する一の位は $3,7$ の $2$ 通りである。

十の位が $2$ のとき、一の位の余りは $2$ であればよい。
該当する一の位は $2,6$ の $2$ 通りである。

ここまでで $3+2+2=7$ 通りである。

十の位を $3$ と同じにする場合、$31$ 未満にするには一の位は $0$ しか選べない。
しかし、$3+0$ は $4$ の倍数ではないので追加はない。

したがって、$0$ 以上 $31$ 未満では $7$ 通りである。
ここから $0$ の $1$ 通りを引く。

答えは $7-1=6$ である。

答えは $10^9+7$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
足し算をするたびに結果を % 1000000007 する。

特になし。