母関数は数え上げや確率の問題で使います。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 + y + z + w)
展開するというのは、右辺の第1項から4つのうちから一つ、第2項から同様に一つ選んで掛け合わせたものの総和を取るということです。
(x + y + z + w)2 = x2 + 2xy + 2xz + ...
ここでx2はブロックが赤赤、xyは赤青を表しています。2xyとなっているのは、係数が赤1枚と青1枚の場合の数を表しています。赤青と青赤で一つずつあるのでこうなります。
ここで、
((x + y + z + w)n + (-x + y + z + w)n) / 2
を考えます。n乗なのでn枚のブロックの塗りわけを考えています。分子の第2項は、赤の枚数が奇数のときに負、偶数のときに正になります。第1項はどちらも正なので、足して2で割ると係数は赤が偶数の項だけ残ります。この係数を全て足し合わせれば赤が偶数の場合の数になります。それにはx, y, z, wに1を入れればよいので、結局赤が偶数の場合の数は、
(4n + 2n) / 2
となります。緑が偶数の場合も同じです。また、
((x + y + z + w)n + (-x + y - z + w)n) / 2
これを考えると、赤と緑が両方偶数、あるいは両方奇数の場合の数を表しています。同様にして、
4n / 2
この3つを足し合わせて全ての場合の数を引くと、赤と緑が両方偶数の場合の数の2倍になります。全ての場合の数は4nなので、
(2((4n + 2n) / 2) + 4n / 2 - 4n) / 2 = 4n - 1 + 2n - 1
となります。簡単になりましたね。Pythonで書くと、
N = 10 ** 9 D = 10007 print (pow(4, N - 1, D) + pow(2, N - 1, D)) % D
