ScalaでProject Euler（55）

Problem 31

場合の数ですね。場合の数や確率を求める問題は、まず母関数の手法が使えるかどうか考えたほうが良いです。この問題はわかりやすいです。

P_k(x) = 1 + x^k + x^2k + ...

という母関数を考えます。各係数はkペンスだけ使ったときの場合の数です。例えば、k = 5として、x¹⁰の係数は1だから1通り、x¹¹の係数は0だからそんな組合せはありません。また、

P₁(x)P₂(x) = (1 + x + x² + x³ + ...)(1 + x² + ...) = 1 + x + 2x² + 2x³ + ...

のx³の係数の2は、(1p, 2p), (1p, 1p, 1p)の2通りを表しています。
この問題は、

P₁(x)P₂(x)P₅(x)...P₂₀₀(x)

のx²⁰⁰の係数を求めるだけです。

type Poly = Array[Int]

val N = 200
val coins = List(1, 2, 5, 10, 20, 50, 100, 200)

def series(c :Int) =
    Array.range(0, N + 1).map(k => if(k % c == 0) 1 else 0)

def mul(f :Poly, g :Poly) = {
    val a = new Poly(N + 1)
    for(k <- Iterator.range(0, N + 1); l <- Iterator.range(0, N - k + 1))
        a(k + l) += f(k) * g(l)
    a
}

def unit() : Array[Int]=
    Iterator.range(0, N + 1).map(k => if(k == 0) 1 else 0).toArray

val f = coins.map(series).foldLeft(unit)(mul)
println (f(N))