Codeforces 507D
問題
leading zeroを許さないn桁の整数x(>0)を考える。
以下の条件を満たすxは何個存在するか？
「y mod k = 0となるy(>0)が、整数xのsuffixになっている」
答えをmod mで答える。
n<=1000
k<=100
m<=10^9
考え方
条件を満たすxを考えるため、suffix候補のb桁のyを考えてみる。
y mod k = 0となるyをsuffixとして持つような(leading zeroを許さない)n桁の整数は、
10^{n-b} - 10^{n-b-1} = 9*10^{n-b-1}個存在することがわかる。
ここで各桁でのmod k=0の数と上記の個数を掛け合わせたものを足し合わせていけば答えが求められるこので、b桁のyでy mod k=0となるような整数xは除いた状態で、b+1桁のyでy mod k=0となるような整数xだけを同様に数えていきたい。
b桁のyの先頭に0〜9の数字を加えてb+1桁にする場合、「数字*10^b + y」となるので、b+1桁のyでy mod kの値は、「(数字*10^b + y mod k) mod k」で求められる。
したがって、b桁でmod k=jとなるものは、上記の式から前に付ける数字によってb+1桁でのmod kがどんな値になるかわかる。
b桁とb+1桁の関係性がわかったので、動的計画法で、数えていける。
dp[i][j][l] := yの桁がiで、y mod k = jとなるyをsuffixとして持つn桁の整数の数。ただし、leading zeroを区別するために、i桁のでleading zeroとなる場合l=0、それ以外l=1とする。
10^{kの桁数}までは求められるので、求めておいて、kの桁数からn桁まで求めながら数えていけばよい。
b+1桁目がaであるようなものを考えると、今y mod k = jの場合、次はnextj=(a*10^b + j)%mになり、
各桁で、dp[b][0][1]のものは次の桁では重複考慮したくないので、
・a==0(leading zero)の場合
・dp[b+1][nextj][0] += dp[b][j][0]
・さらに、!=0ならdp[b+1][j][0] += dp[b][j][1]
・a>0(leading zeroじゃない)の場合
・dp[b+1][nextj][1] += dp[b][j][0]
・さらに、j!=0ならdp[b+1][nextj][1] += dp[b][j][1]
・dp[i+1][nextj][0]%=m、dp[i+1][nextj][1]%=m
の関係になっている。
10^bなどは、mod kやmod mでの値が必要なので、前もって計算し、配列などに入れておく。
反省
・範囲外アクセスしないように、多めにとって、ループはnまで
・頭の中のイメージをちゃんと図にしておく
・どの値をどこへ配るか図示
