042 - Multiple of 9（★4）

キーワード

• mod
• 倍数
• DP

解説

問題 (opens in a new tab)

$K \equiv 0 \pmod p \Leftrightarrow (K\text{の各桁の和}) \equiv 0 \pmod p$

に注意すると, Kが 9 の倍数でない時は, 0 を出力し, 9 の倍数の時は, 各位の数字の和がKであるような通りの数を出力すれば良い.

動的計画法を用いる.

各位の和が $n$ であるような通りを dp[n]とする.
各 $j = 1 \dots 9$ について, 各位の和が, $n-j$ であるような整数の一桁目に $j$ をつけると, 各位の和は $n$ となる. 従って, $\textrm{dp}[n] = \Sigma_{i=1}^{9}{\textrm{dp}[n-i]} (n \ge 9)$ が従う.

計算量は $\mathrm{O}(K)$ .

提出コード

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
 
func main() {
	var k int
	scanIntVariables(&k)
	mod := 1000000007
 
	if k%9 != 0 {
		writeLine(0)
		return
	}
 
	dp := make([]int, k+1)
	dp[0] = 1
 
	for i := 1; i <= k; i++ {
		for j := 1; j <= min(i,9); j++ {
			dp[i] += dp[i-j]
			dp[i] %= mod
		}
	}
 
	writeLine(dp[k])
}