feature image

2022年8月30日 | 活動紹介

【競プロer向け】母関数を習得しよう!


tags: 競プロ

【競プロer向け】母関数を習得しよう!

はじめに

この記事は 2022年夏のブログリレー 21 日目の記事です。

こんにちは。20B の tatyam です。

今日は数え上げ問題を解く上で強力な武器となる、母関数を用いた考察テクニックを習得していきましょう。

母関数を用いた考察テクニックは maspy さんの記事 以来広く知られるようになりました。(たぶん)

traP 内の各班では、有志が講師となって 講習会 を行っています。
以下は、最近私が行った FPS 講習会の資料ほぼそのままとなっています。

FPS 講習会

今日は aising2020 F - Two Snuke (Diff : 2741) を解けるようになっていきましょう。

母関数 (generating function)

母関数とは?

数列 母関数

と定義する。

数列について注意

数列は非負整数に対して数が つ定まっている (長さ加算無限の) 数列を考えることにする。
有限の数列を考えたい場合は残りを で埋めて無限数列であるものとする。

母関数の例


母関数は一般に無限個の項があるので、多項式というより 冪級数 (power series) である。(実際、 は多項式ではない。)

この母関数が、数え上げの問題を解くのにとても役に立つ。

演習

  1. 母関数が である数列の先頭 項を答えよ。
  2. 母関数が である数列の先頭 項を答えよ。
  3. 母関数が である数列の先頭 項を答えよ。

まとめ

母関数と線形漸化式

線形漸化式から母関数

問題

数列 の母関数を求めよ。

解答

なので、 を掛けて 要素ずらしたものと、 を掛けて 要素ずらしたものを考える。

より、 である。

母関数から線形漸化式

問題

母関数が である数列の先頭 項を求めよ。

解答

先頭の項から決定していこう。

と置くと、

次の項をみると なので、 に決定

次の項をみると なので、 に決定

次の項をみると なので、 に決定

つまり…?

より、 に決定

より、 に決定

より、 に決定

より、 に決定

つまり…?

母関数の分母が
線形漸化式
DP(もらう場合)
F[n] += F[n - 1]
F[n] += F[n - 2]
DP(配る場合)
F[n + 1] += F[n]
F[n + 2] += F[n]

が対応している。

母関数から線形漸化式の例

問題

母関数が である数列の先頭 項を計算せよ。

解答

解答

で割る もらう DP A[n] += A[n - 1] * 2

を利用する。

注 : 配る DP / もらう DP は計算順序の違いであって DP としては等価なのでどちらでもよい

操作
初期値
A[1] += A[0] * 2
A[2] += A[1] * 2
A[3] += A[2] * 2
A[4] += A[3] * 2

問題

母関数が である数列の先頭 項を計算せよ。

解答

で割る もらう DP A[n] += A[n - 1] * 2 - A[n - 2]

を利用する。

操作
初期値
A[1] += A[0] * 2 - A[-1]
A[2] += A[1] * 2 - A[0]
A[3] += A[2] * 2 - A[1]
A[4] += A[3] * 2 - A[2]

解答

に対応する数列は なので、これを で割る もらう DP A[n] += A[n - 1] 累積和

の累積和を取って、 が答え。

演習

  1. 母関数が である数列の先頭 項を計算せよ。
  2. 母関数が である数列の先頭 項を計算せよ。
  3. 数列 の母関数を求めよ。

まとめ

数列を母関数に

問題

数列 の母関数を求めよ。

解答

同じ数字が 個連続しているから、数列を つに分ける :

と、 が成り立つ。さらに、数列を詰める :

と、 が成り立つ。
より、求める母関数は である。

問題

数列 の母関数を求めよ。

解答

を足すと

となるから、 より、

演習

  1. 数列 の母関数を求めよ。(ヒント : 階差を取ってみよう)

数え上げを母関数に

数列を母関数に変換することで最もうれしいことは、畳み込みが簡単に表現できることである。

畳み込みの例

問題

(互いに区別できない) 円硬貨を 枚、(互いに区別できない) 円硬貨を 枚持っているとき、 円を支払う方法は何通りあるか。

解答

円硬貨のみを使って 円を支払う方法の数を
円硬貨のみを使って 円を支払う方法の数を
とおくと、

が答えである。
これを実際に計算すると、 となる。

畳み込み

数列 から新たな数列

を得る操作を 畳み込み (convolution) という。

畳み込みは冪級数の掛け算と対応していて、それぞれの母関数 に対して が成り立つ。

有限数列の場合を考えれば多項式の話になってわかりやすい。
例えば、 の場合を考えよう。
を展開する。

例えば、 の係数を求めるには、斜めに並んだ を足して とすればよい。
この計算は、畳み込みの式 にほかならない。

畳み込みを使って数える

問題

非負整数 つが出るルーレットがあり、ルーレットを回すと確率 が出る。
このルーレットを 回回したときの出た数の合計が である確率を とするとき、母関数 を母関数 を使って表せ。

解答

回回したときに和が になる確率は で、この母関数は である。
と置くと、 回回したときに和が になる確率は、 なる についての、前 回の和が で後ろ 回が になる確率の和であるから、 で、この母関数は である。
これを繰り返せば、 がわかる。

演習

  1. (互いに区別できない) 円硬貨を無限枚、(互いに区別できない) 円硬貨を無限枚持っているとき、 円を支払う方法の数を とする。母関数 を求めよ。

問題を母関数に帰着する

形式的冪級数 に対して、 と展開したときの の係数 を表す。

問題

https://atcoder.jp/contests/dp/tasks/dp_m

人の子供に 個の区別できない飴を配る。子供 には 個以上 個以下の飴を配らなければならない。配り方は何通りか?

解答

飴の 合計が 個という和の制約があるので、飴の個数が 個の場合の配り方が の係数となる母関数を考える。

子供 へ飴を 個配る方法の数の母関数は、
子供 へ飴を 個配る方法の数の母関数は、
子供 へ飴を合計 個配る方法の数の母関数は、畳み込みになって
子供 へ飴を合計 個配る方法の数の母関数は、畳み込みになって

人の子供へ飴を合計 個配る方法の数の母関数は、 なので、 が答えである。

問題

長さ の数列 がある。
数列 に対して、その うれしさ を総積 で定義する。
数列 の部分列のうち長さが であるもの全てに対してうれしさを計算し、その総和を求めよ。

部分列 : 数列から要素をいくつか ( 個以上) 削除したもの

解答

の各要素に対して 使う・使わない を選び、ちょうど の要素を使うときの総積という形になっている。

そこで、ちょうど 個使うような選び方全てに対してのうれしさの和が の係数となる母関数を考える。
の場合を考えると、母関数は であるから、これを畳み込んで

が答えである。

実際、 のとき、

のとき、

となるから、成り立っていることがわかる。

問題

正整数 が与えられる。以下の条件を満たす正整数列 はいくつ存在するか?

解答

総和が 以下 という和の制約があるので、総和が となる数列の数が の係数となるような母関数を考える。

の場合、母関数は

これを とすると、 の場合の母関数は

実際は であるから総和を取って、目的の母関数は

したがって、

が答え。 が残っていると嫌なので、 で割る 累積和を取って、

とする。

ちなみに : の時点で 時間で求まりそうなことがわかって、最後の式から 時間で求まりそうなことがわかる。

まとめ

母関数から計算方法を復元する

演習

  1. の小さいところで の値を計算し、一般項を推測せよ。

二項係数

注 : 説明の都合上、数列とその母関数を同一視する。

の前 項は 時間で求められる。

で割る 累積和であるから、

これはパスカルの三角形になっているから、

掛け算 (sparse)

数列 個の項以外が全て であるような数列 を掛けたときの前 項は 時間で求められる。

普通に展開すればよい。

を掛けた数列を求めよ。

操作
初期値
A[8] = A[8] * 2 + A[6]
A[7] = A[7] * 2 + A[5]
A[6] = A[6] * 2 + A[4]
A[5] = A[5] * 2 + A[3]
A[4] = A[4] * 2 + A[2]
A[3] = A[3] * 2 + A[1]
A[2] = A[2] * 2 + A[0]
A[1] = A[1] * 2 + A[-1]
A[0] = A[0] * 2 + A[-2]

割り算 (sparse)

数列 個の項以外が全て であるような数列 で割ったときの前 項は 時間で求められる。

分母・分子に適当なものを掛けて分母を の形にして、DP に変換すればよい。

を割った数列の前 項を求めよ。

操作
初期値
A[2] -= A[0] * 2
A[3] -= A[1] * 2
A[4] -= A[2] * 2
A[5] -= A[3] * 2
A[6] -= A[4] * 2
A[7] -= A[5] * 2

掛け算

数列 に数列 を掛けたときの前 項は 時間で求められる。

FFT をすればよい : 【競プロer向け】FFT を習得しよう! | 東京工業大学デジタル創作同好会traP

AC Library にも入っている : Convolution | AC Library

inv, log, exp of FPS

数列 に対して、

詳しくは 形式的冪級数(FPS)の inv,log,exp,pow の定数倍の軽いアルゴリズム | opt の競プロブログ などを参照

pow of FPS

数列 と数 に対して、

これは ができればよい。

演習

  1. 長さ の数列 と長さ の数列 を受け取り、 の前 項を 時間で計算するコードを書け。 であると仮定して良い。

入力例1

7 3
4 -3 2 -1 -1 -4 5
1 0 2

出力例1

4 -3 -6 5 11 -14 -17

入力例2

8 4
1 0 0 0 0 0 0 0
1 -1 -1 -1

出力例2

1 1 2 4 7 13 24 44

入力例3

8 4
1 7 21 35 35 21 7 1
1 3 3 1

出力例3

1 4 6 4 1 0 0 0

母関数から計算方法を復元する例

問題

長さ の数列 と整数 が与えられる。 時間で求めよ。

注 : 数がどれだけ大きくても四則演算は 時間でできるものとする (よくあるのは で計算する)

解答

の前 項は 時間で計算できる。
畳み込みで の前 項を求めるには 時間かかるが、 項目だけなら 時間で計算できる。

実装

N, K = map(int, input().split())
A = list(map(int, input().split()))

# 1 / (1 - x)^K の前 N + 1 項を O(N) 時間で求める
# B[n] = [x^n](1 - x)^-K = binom(n - 1 + K, n - 1)
B = [1]
for i in range(N):
    B.append(B[i] * (N - 1 + K - i) // (i + 1))

# [x^N] (A * B) を O(N) 時間で求める
ans = 0
for i in range(N + 1):
    ans += A[i] * B[N - i]

print(ans)

問題

https://atcoder.jp/contests/dp/tasks/dp_m

人の子供に 個の区別できない飴を配る。子供 には 個以上 個以下の飴を配らなければならない。配り方は何通りか?

時間で求めよ。

解答

必要なのは 項目であるから、計算途中において 項目より先を計算する必要はない。

を掛ける操作、 で割る操作は 時間でできるから、全体で 時間である。

ポイント : 本来、「累積和を使って DP する」という考察が必要なところが機械的にできている。

問題

時間で求めよ。

解答

今度は を掛ける操作、 で割る操作に 時間かけることができない。

と変形すると、 は二項係数になるから簡単に計算できる。
分子の の前 項は 時間で計算できるが、 を展開すると高々 項しかないことから、 に関係なく 時間で計算できる。

分子が と展開されるものとすると、

時間で求められるから、全体で 時間である。

ポイント : 本来、包除原理を使った考察が必要なところが機械的にできている。

問題

数列 に対して、 の前 項を 時間で求めよ。

解答

の前 項は pow of FPS を使って 時間で求まる。
の前 項は inv of FPS を使って 時間で求まる。
これを畳み込めば、 の前 項は 時間で求まる。

を求める

行列累乗

長さ の数列 と長さ の数列 に対して、 時間で求められる。

項を求めておき、分母を線形漸化式に変換して、 要素シフトする行列を作り、行列累乗をすればよい。

を求める。
分母が 線形漸化式 であるから、

が成り立ち、

である。これは行列累乗で 時間で計算できる。

高速きたまさ法 (Feduccia's algorithm)、 (Bostan–Mori algorithm)

↑ は 時間で計算できる。

詳しくは 線形漸化式の高速計算 | Nyaan’s Library などを参照

演習

今なら aising2020 F - Two Snuke が解けるはず…!

  1. を満たす整数の組 全てについて を合計したものを とする。 を求めよ。
  2. 母関数 を求めよ。(ヒント : 階差を取ってみよう)
  3. 元の問題 の答えを の形式で表せ。
  4. どれくらいの時間計算量で解けるか?

おまけ

オンライン整数列大辞典

有名な整数列がたくさん載っている辞典。母関数がわからないとき、一般項がわからないとき、ここで調べるとみつかるかも?

https://oeis.org/search?q=0%2C1%2C2%2C4%2C6%2C9%2C12

b(n) = A002620(n+2) = number of multigraphs with loops on 2 nodes with n edges [so g.f. for b(n) is 1/((1-x)^2*(1-x^2))].

g.f. (Generating Functiion) で母関数が書いてあったり、漸化式が書いてあったり、一般項が書いてあったりする。

FFT マージテク

個の多項式 があり、次数の合計が であるとき、総積の係数 で求められる。

などをするとできる。

実装

F = deque([f_1, …, f_M])
while len(F) > 1:
    a = F.popleft()
    b = F.popleft()
    F.append(convolution(a, b))

長さ の数列 がある。
数列 に対して、その うれしさ を総積 で定義する。
数列 の部分列のうち長さが であるもの全てに対してうれしさを計算し、その総和を求めよ。

で求められる。

exp-log

数列 に対して、 の前 項は 時間で求められる。

問題

から までの 分割数 時間で求めよ。

解答

分割数は以下の問題と同じである。

(互いに区別できない) 円硬貨を無限枚、 円硬貨を無限枚、 円硬貨を無限枚、 円硬貨を無限枚、……
持っているとき、 円を支払う方法は何通りか?

円硬貨のみを用いて 円を支払う方法の数の母関数は
円より大きな硬貨には意味がないから、分割数の母関数は である。

ここで、 とおくと、

時間で計算できるから、 の前 項が計算できれば良い。

より、 がわかる。( 時間かけて の前 項を計算しても良い。)

であるから、 の前 項のうちに非 の項は高々 個しか存在しない。

したがって、調和級数を考えれば 時間で求められる。

[多項式・形式的べき級数] 高速に計算できるものたち | maspyのHP

他にも書こうとしたけど、ここに網羅されてたのでここを見ましょう

おわりに

明日は @mehm8128 さんの記事です! :tanosimi-:

tatyam icon
この記事を書いた人
tatyam

競技プログラミングと音ゲーと素数大富豪をしています。 AtCoder銅冠 (https://atcoder.jp/users/tatyam) ICPC 2020 Asia Yokohama Regional 3 位 (good_yamikin) ICPC 2021 Asia Yokohama Regional 3 位 (tonosama)

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2022年4月7日
traPグラフィック班の活動紹介
annin icon annin
2021年8月12日
CPCTFを支えたWebshell
mazrean icon mazrean
2021年5月19日
CPCTF2021を実現させたスコアサーバー
xxpoxx icon xxpoxx
2021年3月19日
traPグラフィック班の活動紹介
NABE icon NABE
2022年9月26日
競プロしかシラン人間が web アプリ QK Judge を作った話
tqk icon tqk
2022年9月16日
5日でゲームを作った #tararira
Komichi icon Komichi
記事一覧 タグ一覧 Google アナリティクスについて