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

まず k に $1$ を足す。
これにより、$0$ 以上 $31$ 未満の数を数え、最後に 0 の分を引く形にしている。

k: 31

free[i][j] を、i 桁目より後ろを自由に決めたとき、桁和を $d$ で割った余りが j になるものの数とする。

最下位桁より後ろには何もないので、次の状態から始まる。

free[1]: {1, 0, 0, 0}

下の桁を $1$ 桁自由に決めると、0 から 9 の $10$ 通りになる。

free[0]: {3, 3, 2, 2}

上から $1$ 桁目で、3 より小さい 0,1,2 を置く場合を数える。

0 を置く: free[0][0] = 3
1 を置く: free[0][3] = 2
2 を置く: free[0][2] = 2

ここまでで $7$ 通りである。
次の桁で 1 より小さい 0 を置く場合は、残り桁がないため追加は $0$ 通りである。

最後に 0 の分を引く。

7 - 1 = 6

よって答えは $6$ である。

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

特になし。