桁DP
問題 問題概要 N以下の正整数であって、十進法表記したときの各桁の数の和がDの倍数であるものの個数をmod 1e9+7で求めよ。 1<=D<=102,1<=N<=10104 解法 dp[0][i][j] := (下からi桁までの数で、modがjであるものの数) dp[1][i][j] := (下からi桁までの数で、…
問題 問題概要 N以下の正整数であって、十進法表記したときの各桁の数の和がDの倍数であるものの個数をmod 1e9+7で求めよ。 1<=D<=102,1<=N<=10104 解法 dp[0][i][j] := (下からi桁までの数で、modがjであるものの数) dp[1][i][j] := (下からi桁までの数で、…