母関数 - inamori’s diary

母関数は数え上げや確率の問題で使います。Project Eulerではときどき使えるのでおぼえましょう。最近ではProblem 286で使いました。例えばこんな問題で使えます。 N個のブロックが横一列に並んでいます。赤・青・緑・黄の4色のペンキがあり、これらで各ブロックを塗っていきます。赤色で塗られたブロックの個数と、緑色で塗られたブロックの個数がともに偶数個となるような塗り方の総数を求め、10007で割った余りを出力しなさい。 プログラミングコンテストチャレンジブックP.182 この本の中では行列を使って解いていますが、母関数を使うとほとんどコーディングしなくてもよくなります。 まず、 (x + y + z + w)2 を考えます。xを赤、yを青、zを緑、wを黄とみなします。そうしてこれを展開することを考えます。 (x + y + z + w)2 = (x + y + z + w)(x