---
tags: 競プロ
---
# FPS 講習会
今日は [aising2020 F - Two Snuke](https://atcoder.jp/contests/aising2020/tasks/aising2020_f) (Diff : 2741) を解けるようになっていきましょう。
## 母関数 (generating function)
### 母関数とは？
数列 $A = (A_0, A_1, A_2, …)$ の **母関数** を
$$
A(x) = A_0 + A_1x + A_2x^2 + \cdots = \sum_{n = 0}^\infty A_n x^n
$$
と定義する。
##### 数列について注意
数列は非負整数に対して数が $1$ つ定まっている (長さ加算無限の) 数列を考えることにする。
有限の数列を考えたい場合は残りを $0$ で埋めて無限数列であるものとする。
### 母関数の例
- 数列 $A = (3, 2, 1, 0, 0, 0, …)$ の母関数は $A(x) = x^2 + 2x + 3$ である。
- 数列 $B = (1, 1, 1, …)$ の母関数は $B(x) = 1 + x + x^2 + \cdots$ である。
- 数列 $C = (\frac{1}{0!}, \frac{1}{1!}, \frac{1}{2!}, …)$ の母関数は $C(x) = \frac{1}{0!} + \frac{1}{1!}x + \frac{1}{2!}x^2 + \cdots = e^x$ である。
---
母関数は一般に無限個の項があるので、多項式というより [冪級数 (power series)](https://ja.wikipedia.org/wiki/%E5%86%AA%E7%B4%9A%E6%95%B0) である。(実際、$e^x$ は多項式ではない。)
この母関数が、数え上げの問題を解くのにとても役に立つ。
## 形式的冪級数 (formal power series)
### 形式的冪級数とは？
母関数に値を代入し、例えば $C(1) = e$ とか、$B(2) = \infty$ のような値を調べることに意味はあまりない。(大抵の場合発散してしまう)
例えば、$\displaystyle B(x) =\sum_{n=0}^\infty x^n = \frac{1}{1 - x}$ という式は $|x| < 1$ のときには成り立つが、$|x| ≥ 1$ のときには左辺が発散して成り立たない。
しかし、$x$ に具体的な値を入れることを考えないのだから、このような発散する場合を無視した変形も許してしまう冪級数が、**形式的冪級数** である。(複素関数論 ([一致の定理](https://ja.wikipedia.org/wiki/%E4%B8%80%E8%87%B4%E3%81%AE%E5%AE%9A%E7%90%86) とか) をやると正当性がわかるぞ！)
$\displaystyle\sum_{n=0}^\infty x^n = \frac{1}{1 - x}$ と変形することで、無限和がより簡単な形になってうれしい！
以降母関数は形式的冪級数であるものとし、発散する場合を無視していろいろな変形を行う。
### 演習
1. 母関数が $\dfrac{x^2}{1 - x}$ である数列の先頭 $5$ 項を答えよ。
2. 母関数が $\dfrac{1}{1 - x^2}$ である数列の先頭 $5$ 項を答えよ。
3. 母関数が $\cos(x)$ である数列の先頭 $5$ 項を答えよ。
### まとめ
- 数列に対して母関数 $\displaystyle A(x) = \sum_{n = 0}^\infty A_n x^n$ を考える。
- 母関数をマクローリン展開すると数列が復元できる。
- 発散する場合を無視した変形をしても対応する数列は変わらないので OK
## 母関数と線形漸化式
### 線形漸化式から母関数
#### 問題
数列 $\begin{cases}F_0 = 1 \\ F_1 = 1 \\ F_n = F_{n - 1} + F_{n - 2}\end{cases}$ の母関数を求めよ。
#### 解答
$F_n = F_{n - 1} + F_{n - 2}$ なので、$F(x)$ に $x$ を掛けて $1$ 要素ずらしたものと、$x^2$ を掛けて $2$ 要素ずらしたものを考える。
$$
\begin{aligned}
F(x) &=& 1 + 1x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + \cdots\\
xF(x) &=& 1x + 1x^2 + 2x^3 + 3x^4 + 5x^5 + \cdots\\
x^2F(x) &=& 1x^2 + 1x^3 + 2x^4 + 3x^5 + \cdots\\
\hline
(1 - x - x^2)F(x) &=& 1\hspace{15.5em}
\end{aligned}
$$
より、$F(x) = \dfrac{1}{1 - x - x^2}$ である。
### 母関数から線形漸化式
#### 問題
母関数が $\dfrac{1}{1 - x - x^2}$ である数列の先頭 $5$ 項を求めよ。
#### 解答
$$
\frac{1}{1 - x - x^2} = \frac{1}{1 - (x + x^2)} = 1 + (x + x^2) + (x + x^2)^2 + (x + x^2)^3 + \cdots
$$
##### 先頭の項から決定していこう
$$
\sum_{n=0}^0(x + x^2)^n = 1
$$
$0$ 次の項はこれだけなので、$F_0 = 1$ に決定
$$
\begin{aligned}
\sum_{n=0}^0(x + x^2)^n &= 1\\
(x + x^2)\sum_{n=0}^0(x + x^2)^n &= 0 + 1x + 1x^2\\
\sum_{n=0}^1(x + x^2)^n &= 1 + 1x + 1x^2\\
\end{aligned}
$$
$1$ 次の項はこれだけなので、$F_1 = 1$ に決定
$$
\begin{aligned}
\sum_{n=0}^1(x + x^2)^n &= 1 + 1x + 1x^2\\
(x + x^2)\sum_{n=0}^1(x + x^2)^n &= 0 + 1x + 2x^2 + 2x^3 + 1x^4\\
\sum_{n=0}^2(x + x^2)^n &= 1 + 1x + 2x^2 + 2x^3 + 1x^4\\
\end{aligned}
$$
$2$ 次の項はこれだけなので、$F_2 = 2$ に決定
つまり…？
| $F_0$ | $F_1$ | $F_2$ | $F_3$ | $F_4$ |
| ----- | ----- | ----- | ----- | ----- |
| $\bf 1$ | | | | |
$F_0 = 1$ に決定
$(x + x^2)$ を掛けて $1$ を足す
| $F_0$ | $F_1$ | $F_2$ | $F_3$ | $F_4$ |
| ----- | ----- | ----- | ----- | ----- |
| $1$ | $\bf 1$ | ？ | | |
$F_1 = 1$ に決定
$(x + x^2)$ を掛けて $1$ を足す
| $F_0$ | $F_1$ | $F_2$ | $F_3$ | $F_4$ |
| ----- | ----- | ----- | ----- | ----- |
| $1$ | $1$ | $\bf 2$ | ？ | ？ |
$F_2 = 2$ に決定
$(x + x^2)$ を掛けて $1$ を足す
| $F_0$ | $F_1$ | $F_2$ | $F_3$ | $F_4$ |
| ----- | ----- | ----- | ----- | ----- |
| $1$ | $1$ | $2$ | $\bf 3$ | ？ |
$F_3 = 3$ に決定
$(x + x^2)$ を掛けて $1$ を足す
| $F_0$ | $F_1$ | $F_2$ | $F_3$ | $F_4$ |
| ----- | ----- | ----- | ----- | ----- |
| $1$ | $1$ | $2$ | $3$ | $\bf 5$ |
$F_4 = 5$ に決定
つまり…？
|母関数の分母が<br/>$1 - x - x^2$|線形漸化式<br/>$F_n = F_{n - 1} + F_{n - 2}$|DP(もらう場合)<br/>`F[n] += F[n - 1]`<br/>`F[n] += F[n - 2]`|DP(配る場合)<br/>`F[n + 1] += F[n]`<br/>`F[n + 2] += F[n]`|
| --- | --- | --- | --- |
が対応している。
### 母関数から線形漸化式の例
#### 問題
母関数が $\dfrac{1 - x^2}{1 - 2x}$ である数列の先頭 $5$ 項を計算せよ。
#### 解答 $1$
$$
\begin{aligned}
\frac{1}{1 - 2x} &= 1 + 2x + 4x^2 + 8x^3 + 16x^4 + \cdots\\
\frac{-x^2}{1 - 2x} &= 0 + 0x -1x^2 - 2x^3 - 4x^4 + \cdots\\
\hline
\frac{1-x^2}{1 - 2x} &= 1 + 2x + 3x^2 + 6x^3 + 12x^4 + \cdots\\
\end{aligned}
$$
#### 解答 $2$
$1 - 2x$ で割る $\iff$ もらう DP `A[n] += A[n - 1] * 2`
を利用する。
注 : 配る DP / もらう DP は計算順序の違いであって DP としては等価なのでどちらでもよい
| $A_0$ | $A_1$ | $A_2$ | $A_3$ | $A_4$ | 操作 |
| ----- | ----- | ----- | ----- | ----- | ------------------ |
| $\bf 1$ | $0$ | $-1$ | $0$ | $0$ | 初期値 $1 - x^2$ |
| $1$ | $\bf 2$ | $-1$ | $0$ | $0$ | `A[1] += A[0] * 2` |
| $1$ | $2$ | $\bf 3$ | $0$ | $0$ | `A[2] += A[1] * 2` |
| $1$ | $2$ | $3$ | $\bf 6$ | $0$ | `A[3] += A[2] * 2` |
| $1$ | $2$ | $3$ | $6$ | $\bf 12$ | `A[4] += A[3] * 2` |
#### 問題
母関数が $\dfrac{1}{1 - 2x + x^2}$ である数列の先頭 $5$ 項を計算せよ。
#### 解答 $1$
$1 - 2x + x^2$ で割る $\iff$ もらう DP `A[n] += A[n - 1] * 2 - A[n - 2]`
を利用する。
| $A_0$ | $A_1$ | $A_2$ | $A_3$ | $A_4$ | 操作 |
| ----- | ----- | ----- | ----- | ----- | --------------------------------- |
| $\bf 1$ | $0$ | $0$ | $0$ | $0$ | 初期値 $1$ |
| $1$ | $\bf 2$ | $0$ | $0$ | $0$ | `A[1] += A[0] * 2 - A[-1]` |
| $1$ | $2$ | $\bf 3$ | $0$ | $0$ | `A[2] += A[1] * 2 - A[0]` |
| $1$ | $2$ | $3$ | $\bf 4$ | $0$ | `A[3] += A[2] * 2 - A[1]` |
| $1$ | $2$ | $3$ | $4$ | $\bf 5$ | `A[4] += A[3] * 2 - A[2]` |
#### 解答 $2$
$\dfrac{1}{1 - 2x + x^2} = \dfrac{1}{(1 - x)^2}$
$\dfrac{1}{1 - x}$ に対応する数列は $(1, 1, 1, 1, 1, …)$ なので、これを $1 - x$ で割る $\iff$ もらう DP `A[n] += A[n - 1]` $\iff$ 累積和
$(1, 1, 1, 1, 1, …)$ の累積和を取って、$(1, 2, 3, 4, 5, …)$ が答え。
### 演習
4. 母関数が $\dfrac{1 - x^4}{1 - x}$ である数列の先頭 $5$ 項を計算せよ。
5. 母関数が $\dfrac{2}{2 - x}$ である数列の先頭 $5$ 項を計算せよ。
6. 数列 $\begin{cases} T_0 = 1 \\ T_1 = 1 \\ T_2 = 1 \\ T_n = T_{n - 1} + T_{n - 2} + T_{n - 3}\end{cases}$ の母関数を求めよ。
### まとめ
- 母関数を $1 - ax - bx^2 + \cdots$ で割ることは、もらう DP<br/>`A[n] += A[n - 1] * a + A[n - 2] * b + …` を計算することに対応する。
- 特に、母関数を $1 - x$ で割ることは、累積和に対応する。
### 数列を母関数に
#### 問題
数列 $A = (1, 1, 2, 2, 3, 3, 4, 4, …)$ の母関数を求めよ。
#### 解答
同じ数字が $2$ 個連続しているから、数列を $2$ つに分ける :
$$
B = (1, 0, 2, 0, 3, 0, 4, 0, …)\\
C = (0, 1, 0, 2, 0, 3, 0, 4, …)\\
$$
と、$C(x) = xB(x),\ A(x) = (1 + x)B(x)$ が成り立つ。さらに、数列を詰める :
$$
D = (1, 2, 3, 4, …)
$$
と、$D(x^2) = B(x)$ が成り立つ。
$D(x) = \dfrac{1}{(1 - x)^2}$ より、求める母関数は $\dfrac{1 + x}{(1 - x^2)^2}$ である。
#### 問題
数列 $A = (1, 3, 7, 15, 31, 63, …)$ の母関数を求めよ。
#### 解答
$$
B = (1, 1, 1, 1, 1, 1, …)\\
$$
を足すと
$$
A + B = (2, 4, 8, 16, 32, 64, …)\\
$$
となるから、$B(x) = \dfrac{1}{1 - x},\ A(x) + B(x) = \dfrac{2}{1 - 2x}$ より、
$$
A(x) = \frac{2}{1 - 2x} - \frac{1}{1 - x} = \frac{1}{(1 - x)(1 - 2x)}
$$
### 演習
7. 数列 $A = (0, 1, 4, 9, 16, 25, …)$ の母関数を求めよ。(ヒント : <span style="color:white">階差を取ってみよう</span>)
## 数え上げを母関数に
数列を母関数に変換することで最もうれしいことは、畳み込みが簡単に表現できることである。
### 畳み込みの例
#### 問題
(互いに区別できない) $1$ 円硬貨を $4$ 枚、(互いに区別できない) $2$ 円硬貨を $2$ 枚持っているとき、$n$ 円を支払う方法は何通りあるか。
#### 解答
$1$ 円硬貨のみを使って $x$ 円を支払う方法の数を $A = (1, 1, 1, 1, 1)$
$2$ 円硬貨のみを使って $y$ 円を支払う方法の数を $B = (1, 0, 1, 0, 1)$
とおくと、
$$
C_n = \sum_{i+j=n}A_i B_j
$$
が答えである。
これを実際に計算すると、$C = (1, 1, 2, 2, 3, 2, 2, 1, 1)$ となる。
### 畳み込み
数列 $A, B$ から新たな数列
$$
C_n = \sum_{i+j=n}A_i B_j
$$
を得る操作を **畳み込み** (convolution) という。
畳み込みは形式的冪級数の掛け算と対応していて、それぞれの母関数 $A(x), B(x), C(x)$ に対して $C(x) = A(x) \times B(x)$ が成り立つ。
有限数列の場合を考えれば多項式の話になってわかりやすい。
例えば、$A = (1, 2, 3), B = (1, -1, 1)$ の場合を考えよう。
$A(x) \times B(x) = (1 + 2x + 3x^2) \times (1 - x + x^2)$ を展開する。
| $\times$ | $\boldsymbol{1}$ | $\boldsymbol{2x}$ | $\boldsymbol{3x^2}$ |
| -------- | ----- | ------- | ------- |
| $\boldsymbol{1}$ | $1$ | $2x$ | $3x^2$ |
| $\boldsymbol{-x}$ | $-x$ | $-2x^2$ | $-3x^3$ |
| $\boldsymbol{x^2}$ | $x^2$ | $2x^3$ | $3x^4$ |
例えば、$A(x) \times B(x)$ の $x^2$ の係数を求めるには、斜めに並んだ $3x^2,- 2x^2, x^2$ を足して $2x^2$ とすればよい。
この計算は、畳み込みの式 $\displaystyle C_2 = \sum_{i + j = 2}A_i B_j$ にほかならない。
### 畳み込みを使って数える
#### 問題
非負整数 $1$ つが出るルーレットがあり、ルーレットを回すと確率 $P_n$ で $n$ が出る。
このルーレットを $10$ 回回したときの出た数の合計が $m$ である確率を $Q_m$ とするとき、母関数 $Q(x)$ を母関数 $P(x)$ を使って表せ。
#### 解答
$2$ 回回したときに和が $n$ になる確率は $\displaystyle\sum_{i+j=n}P_iP_j$ で、この母関数は $(P(x))^2$ である。
$P'(x) = (P(x))^2$ と置くと、$3$ 回回したときに和が $n$ になる確率は、$i + j = n$ なる $(i, j)$ についての、前 $2$ 回の和が $i$ で後ろ $1$ 回が $j$ になる確率の和であるから、$\displaystyle\sum_{i+j=n}P'_iP_j$ で、この母関数は $(P(x))^3$ である。
これを繰り返せば、$Q(x) = (P(x))^{10}$ がわかる。
### 演習
8. (互いに区別できない) $1$ 円硬貨を無限枚、(互いに区別できない) $2$ 円硬貨を無限枚持っているとき、$n$ 円を支払う方法の数を $A_n$ とする。母関数 $A(x)$ を求めよ。
### 問題を母関数に帰着する
形式的冪級数 $f(x)$ に対して、$[x^n]f(x)$ で $f(x) = \displaystyle \sum_{i = 0}^\infty f_ix^i$ と展開したときの $x^n$ の係数 $(f_n)$ を表す。
#### 問題
https://atcoder.jp/contests/dp/tasks/dp_m
$N$ 人の子供に $K$ 個の区別できない飴を配る。子供 $i$ には $0$ 個以上 $A_i$ 個以下の飴を配らなければならない。配り方は何通りか？
#### 解答
飴の **合計が** $K$ 個という和の制約があるので、飴の個数が $n$ 個の場合の配り方が $x^n$ の係数となる母関数を考える。
子供 $1$ へ飴を $n$ 個配る方法の数の母関数は、$\displaystyle\sum_{n=0}^{A_1}x^n = \frac{1 - x^{A_1 + 1}}{1 - x}$
子供 $2$ へ飴を $n$ 個配る方法の数の母関数は、$\displaystyle\sum_{n=0}^{A_2}x^n = \frac{1 - x^{A_2 + 1}}{1 - x}$
子供 $1, 2$ へ飴を合計 $n$ 個配る方法の数の母関数は、畳み込みになって $\dfrac{1 - x^{A_1 + 1}}{1 - x}\cdot\dfrac{1 - x^{A_2 + 1}}{1 - x}$
子供 $1, 2, 3$ へ飴を合計 $n$ 個配る方法の数の母関数は、畳み込みになって $\dfrac{1 - x^{A_1 + 1}}{1 - x}\cdot\dfrac{1 - x^{A_2 + 1}}{1 - x}\cdot\dfrac{1 - x^{A_3 + 1}}{1 - x}$
$N$ 人の子供へ飴を合計 $n$ 個配る方法の数の母関数は、$\displaystyle\prod_{i=1}^N\frac{1 - x^{A_i + 1}}{1 - x}$ なので、$\displaystyle[x^K]\left(\prod_{i=1}^N\frac{1 - x^{A_i + 1}}{1 - x}\right)$ が答えである。
#### 問題
長さ $N$ の数列 $A = (A_1, …, A_N)$ がある。
数列 $X = (X_1, …, X_{|X|})$ に対して、その **うれしさ** を総積 $\displaystyle\prod_{i=1}^{|X|}X_i$ で定義する。
数列 $A$ の部分列のうち長さが $M$ であるもの全てに対してうれしさを計算し、その総和を求めよ。
部分列 : 数列から要素をいくつか ($0$ 個以上) 削除したもの
#### 解答
$A$ の各要素に対して 使う・使わない を選び、**ちょうど $M$ 個** の要素を使うときの総積という形になっている。
そこで、ちょうど $m$ 個使うような選び方全てに対してのうれしさの和が $x^m$ の係数となる母関数を考える。
$N = 1$ の場合を考えると、母関数は $1 + A_1x$ であるから、これを畳み込んで
$$
[x^M]\left(\prod_{i=1}^N1 + A_ix\right)
$$
が答えである。
実際、$N = 2$ のとき、
$$
1 + (A_1 + A_2)x + A_1A_2 x^2 = (1 + A_1x)(1 + A_2x)
$$
$N = 3$ のとき、
$$
1 + (A_1 + A_2 + A_3)x + (A_1A_2 + A_1A_3 + A_2A_3) x^2 + A_1A_2A_3x^3 = (1 + A_1x)(1 + A_2x)(1 + A_3x)
$$
となるから、成り立っていることがわかる。
#### 問題
正整数 $N, M, K$ が与えられる。以下の条件を満たす正整数列 $A = (A_1, A_2, …, A_{|A|})$ はいくつ存在するか？
- $1 ≤ |A| ≤ N$
- $1 ≤ A_i ≤ M\ (1 ≤ i ≤ |A|)$
- $\left(\displaystyle\sum_n A_n\right) ≤ K$
#### 解答
**総和が $K$ 以下** という和の制約があるので、総和が $n$ となる数列の数が $x^n$ の係数となるような母関数を考える。
$|A| = 1$ の場合、母関数は $\displaystyle\sum_{n=1}^{M}x^n = \frac{x - x^{M + 1}}{1 - x}$
これを $f(x)$ とすると、$|A| = n$ の場合の母関数は $(f(x))^n$
実際は $1 ≤ |A| ≤ N$ であるから総和を取って、目的の母関数は
$$
\begin{aligned}
\sum_{n = 1}^N(f(x))^n &= \frac{f(x) - (f(x))^{N+1}}{1 - f(x)}\\
&= \frac{x - x^{M+1}}{(1 - x) - (x - x^{M+1})} - \frac{(x - x^{M+1})(f(x))^{N}}{(1 - x) - (x - x^{M+1})}\\
&= \frac{x - x^{M+1}}{1 - 2x + x^{M+1}} - \frac{(x - x^{M+1})^{N+1}}{(1-x)^N(1 - 2x + x^{M+1})}\\
\end{aligned}
$$
したがって、
$$
\sum_{k=1}^K[x^k]\left(\frac{x - x^{M+1}}{1 - 2x + x^{M+1}} - \frac{(x - x^{M+1})^{N+1}}{(1-x)^N(1 - 2x + x^{M+1})}\right)
$$
が答え。$\sum$ が残っていると嫌なので、$1-x$ で割る $\iff$ 累積和を取って、
$$
[x^K]\left(\frac{x - x^{M+1}}{(1-x)(1 - 2x + x^{M+1})} - \frac{(x - x^{M+1})^{N+1}}{(1-x)^{N+1}(1 - 2x + x^{M+1})}\right)
$$
とする。
ちなみに : $\frac{f(x) - (f(x))^{N+1}}{1 - f(x)}$ の時点で $O(K \log K)$ 時間で求まりそうなことがわかって、最後の式から $O(K)$ 時間で求まりそうなことがわかる。
### まとめ
- 「総和がちょうど $X$」や「総和が $X$ 以下」のような総和の制約があり、確率 や 組み合わせの数 など、掛け算をするものを数える場合、母関数の掛け算で表すことができる。
- 「どのように DP をするかを考察する」という難しいパートが「母関数に変換する」→「簡単な式に変形する」→「式から計算方法を復元する」となり、比較的機械的にできるようになる。
## 母関数から計算方法を復元する
### 演習
9. $(N, K)$ の小さいところで $\displaystyle[x^K]\frac{1}{(1 - x)^N}\quad(N ≥ 1)$ の値を計算し、一般項を推測せよ。
### 二項係数
注 : 説明の都合上、数列とその母関数を同一視する。
$\dfrac{1}{(1 - x)^n}$ の前 $N$ 項は $O(N)$ 時間で求められる。
$1 - x$ で割る $\iff$ 累積和であるから、
| $(1 - x)^0$ | $1$ | $0$ | $0$ | $0$ |
| ----------- | --- | --- | --- | --- |
| $(1 - x)^{-1}$ | $1$ | $1$ | $1$ | $1$ |
| $(1 - x)^{-2}$ | $1$ | $2$ | $3$ | $4$ |
| $(1 - x)^{-3}$ | $1$ | $3$ | $6$ | $10$ |
| $(1 - x)^{-3}$ | $1$ | $4$ | $10$ | $20$ |
これはパスカルの三角形になっているから、
$\displaystyle\frac{1}{(1 - x)^n} = \sum_{k=0}^\infty\binom{n-1+k}{k}x^k$
### 掛け算 (sparse)
数列 $\displaystyle A(x) = \sum_{n=0}^\infty A_nx^n$ に $K$ 個の項以外が全て $0$ であるような数列 $\displaystyle B(x) = \sum_{k=1}^K b_kx^{n_k}$ を掛けたときの前 $N$ 項は $O(NK)$ 時間で求められる。
普通に展開すればよい。
#### 例
$A(x) = 4 - 3x + 2x^2 - x^3 - x^4 - 4x^5 + 5x^6$ に $B(x) = 2 + x^2$ を掛けた数列を求めよ。
| $A_0$ | $A_1$ | $A_2$ | $A_3$ | $A_4$ | $A_5$ | $A_6$ | $A_7$ | $A_8$ | 操作 |
| ------- | -------- | ------- | -------- | ------- | -------- | ------- | -------- | ------- | ------------------------- |
| $4$ | $-3$ | $2$ | $-1$ | $-1$ | $-4$ | $5$ | $0$ | $0$ | 初期値 |
| $4$ | $-3$ | $2$ | $-1$ | $-1$ | $-4$ | $5$ | $0$ | $\bf 5$ | `A[8] = A[8] * 2 + A[6]` |
| $4$ | $-3$ | $2$ | $-1$ | $-1$ | $-4$ | $5$ | $\bf -4$ | $5$ | `A[7] = A[7] * 2 + A[5]` |
| $4$ | $-3$ | $2$ | $-1$ | $-1$ | $-4$ | $\bf 9$ | $-4$ | $5$ | `A[6] = A[6] * 2 + A[4]` |
| $4$ | $-3$ | $2$ | $-1$ | $-1$ | $\bf -9$ | $9$ | $-4$ | $5$ | `A[5] = A[5] * 2 + A[3]` |
| $4$ | $-3$ | $2$ | $-1$ | $\bf 0$ | $-9$ | $9$ | $-4$ | $5$ | `A[4] = A[4] * 2 + A[2]` |
| $4$ | $-3$ | $2$ | $\bf -5$ | $0$ | $-9$ | $9$ | $-4$ | $5$ | `A[3] = A[3] * 2 + A[1]` |
| $4$ | $-3$ | $\bf 8$ | $-5$ | $0$ | $-9$ | $9$ | $-4$ | $5$ | `A[2] = A[2] * 2 + A[0]` |
| $4$ | $\bf -6$ | $8$ | $-5$ | $0$ | $-9$ | $9$ | $-4$ | $5$ | `A[1] = A[1] * 2 + A[-1]` |
| $\bf 8$ | $-6$ | $8$ | $-5$ | $0$ | $-9$ | $9$ | $-4$ | $5$ | `A[0] = A[0] * 2 + A[-2]` |
### 割り算 (sparse)
数列 $\displaystyle A(x) = \sum_{n=0}^\infty A_nx^n$ を $K$ 個の項以外が全て $0$ であるような数列 $\displaystyle B(x) = \sum_{k=1}^K b_kx^{n_k}$ で割ったときの前 $N$ 項は $O(NK)$ 時間で求められる。
分母・分子に適当なものを掛けて分母を $1 - f(x)$ の形にして、DP に変換すればよい。
#### 例
$A(x) = 4 - 3x + 2x^2 - x^3 - x^4 - 4x^5 + 5x^6$ を $B(x) = 1 + 2x^2$ を割った数列の前 $8$ 項を求めよ。
| $A_0$ | $A_1$ | $A_2$ | $A_3$ | $A_4$ | $A_5$ | $A_6$ | $A_7$ | 操作 |
| ------- | -------- | -------- | ----- | ----- | ----- | ----- | ----- | ------------------ |
| $\bf 4$ | $\bf -3$ | $2$ | $-1$ | $-1$ | $-4$ | $5$ | $0$ | 初期値 |
| $4$ | $-3$ | $\bf -6$ | $-1$ | $-1$ | $-4$ | $5$ | $0$ | `A[2] -= A[0] * 2` |
| $4$ | $-3$ | $-6$ | $\bf 5$ | $-1$ | $-4$ | $5$ | $0$ | `A[3] -= A[1] * 2` |
| $4$ | $-3$ | $-6$ | $5$ | $\bf 11$ | $-4$ | $5$ | $0$ | `A[4] -= A[2] * 2` |
| $4$ | $-3$ | $-6$ | $5$ | $11$ | $\bf -14$ | $5$ | $0$ | `A[5] -= A[3] * 2` |
| $4$ | $-3$ | $-6$ | $5$ | $11$ | $-14$ | $\bf -17$ | $0$ | `A[6] -= A[4] * 2` |
| $4$ | $-3$ | $-6$ | $5$ | $11$ | $-14$ | $-17$ | $\bf 28$ | `A[7] -= A[5] * 2` |
### 掛け算
数列 $\displaystyle A(x) = \sum_{n=0}^\infty A_nx^n$ に数列 $\displaystyle B(x) = \sum_{n=0}^\infty B_nx^n$ を掛けたときの前 $N$ 項は $O(N\log N)$ 時間で求められる。
FFT をすればよい : [【競プロer向け】FFT を習得しよう！ | 東京工業大学デジタル創作同好会traP](https://trap.jp/post/1386/)
AC Library にも入っている : [Convolution | AC Library](https://atcoder.github.io/ac-library/production/document_ja/convolution.html)
### inv, log, exp of FPS
数列 $\displaystyle A(x) = \sum_{n=0}^\infty A_nx^n$ に対して、
- $\dfrac{1}{A(x)}$ の前 $N$ 項は $O(N \log N)$ 時間で求められる。
- $\displaystyle\log(A(x)) = -\sum_{k=1}^\infty\frac{(1 - A(x))^k}{k} = \int\frac{A'(x)}{A(x)}$ の前 $N$ 項は $O(N \log N)$ 時間で求められる。
- $\displaystyle\exp(A(x)) = \sum_{k=0}^\infty\frac{(A(x))^k}{k!}$ の前 $N$ 項は $O(N \log N)$ 時間で求められる。
詳しくは [形式的冪級数（FPS）の inv，log，exp，pow の定数倍の軽いアルゴリズム | opt の競プロブログ](https://opt-cp.com/fps-fast-algorithms/) などを参照
### pow of FPS
数列 $\displaystyle A(x) = \sum_{n=0}^\infty A_nx^n$ と数 $K$ に対して、
- $(A(x))^K = \exp(K\log(A(x)))$ の前 $N$ 項は $O(N \log N)$ 時間で求められる。
これは $\log$ と $\exp$ ができればよい。
### 演習
10. 長さ $N$ の数列 $\displaystyle A(x) = \sum_{n=0}^{N-1} A_nx^n$ と長さ $M$ の数列 $\displaystyle B(x) = \sum_{n=0}^{M-1} B_nx^n$ を受け取り、$\dfrac{A(x)}{B(x)}$ の前 $N$ 項を $O(NM)$ 時間で計算するコードを書け。$B_0 = 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+1$ の数列 $\displaystyle A(x) = \sum_{n = 0}^{N}A_nx^n$ と整数 $K ≥ 0$ が与えられる。$[x^N]\dfrac{A(x)}{(1 - x)^K}$ を $O(N)$ 時間で求めよ。
注 : 数がどれだけ大きくても四則演算は $O(1)$ 時間でできるものとする (よくあるのは $\bmod{998244353}$ で計算する)
#### 解答
$\dfrac{1}{(1-x)^K}$ の前 $N + 1$ 項は $O(N)$ 時間で計算できる。
畳み込みで $A(x) \times \dfrac{1}{(1-x)^K}$ の前 $N + 1$ 項を求めるには $O(N \log N)$ 時間かかるが、$N$ 項目だけなら $O(N)$ 時間で計算できる。
#### 実装
```python=
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
>
> $N$ 人の子供に $K$ 個の区別できない飴を配る。子供 $i$ には $0$ 個以上 $A_i$ 個以下の飴を配らなければならない。配り方は何通りか？
$\displaystyle[x^K]\left(\prod_{i=1}^N\frac{1 - x^{A_i + 1}}{1 - x}\right)$ を $O(NK)$ 時間で求めよ。
#### 解答
必要なのは $K$ 項目であるから、計算途中において $K$ 項目より先を計算する必要はない。
$(1 - x^{A_i + 1})$ を掛ける操作、$(1 - x)$ で割る操作は $O(K)$ 時間でできるから、全体で $O(NK)$ 時間である。
ポイント : 本来、「累積和を使って DP する」という考察が必要なところが機械的にできている。
#### 問題
$\displaystyle[x^K]\left(\prod_{i=1}^N\frac{1 - x^{A_i + 1}}{1 - x}\right)$ を $O(N2^N)$ 時間で求めよ。
#### 解答
今度は $(1 - x^{A_i + 1})$ を掛ける操作、$(1 - x)$ で割る操作に $O(K)$ 時間かけることができない。
$$
\prod_{i=1}^N\frac{1 - x^{A_i + 1}}{1 - x} = \frac{\prod_{i=1}^N(1 - x^{A_i + 1})}{(1 - x)^N}
$$
と変形すると、$\dfrac{1}{(1 - x)^N}$ は二項係数になるから簡単に計算できる。
分子の $\displaystyle\prod_{i=1}^N(1 - x^{A_i + 1})$ の前 $K + 1$ 項は $O(NK)$ 時間で計算できるが、$\displaystyle\prod_{i=1}^N(1 - x^{A_i + 1})$ を展開すると高々 $2^N$ 項しかないことから、$K$ に関係なく $O(2^N)$ 時間で計算できる。
分子が $\displaystyle\prod_{i=1}^N(1 - x^{A_i + 1}) = \sum_{i=0}^{2^N-1}B_ix^{n_i}$ と展開されるものとすると、
$$
\begin{aligned}
[x^K]\frac{\sum_{i=0}^{2^N-1}B_ix^{n_i}}{(1 - x)^N} &= \sum_{i=0}^{2^N-1}\left(B_i\times[x^{K-n_i}]\frac{1}{(1-x)^N}\right)\\
&= \sum_{i=0}^{2^N-1}B_i\binom{N-1+K-n_i}{K-n_i}\\
&= \sum_{i=0}^{2^N-1}B_i\binom{N-1+K-n_i}{N-1}\\
\end{aligned}
$$
$\displaystyle\binom{N-1+K-n_i}{N-1}$ は $O(N)$ 時間で求められるから、全体で $O(N2^N)$ 時間である。
ポイント : 本来、包除原理を使った考察が必要なところが機械的にできている。
#### 問題
数列 $\displaystyle A(x) = \sum_{n=0}^\infty A_nx^n$ に対して、$\displaystyle\sum_{n=0}^{K-1}(A(x))^n = \frac{1 - (A(x))^K}{1 - A(x)}$ の前 $N$ 項を $O(N \log N)$ 時間で求めよ。
#### 解答
$(A(x))^K$ の前 $N$ 項は [pow of FPS](#pow-of-FPS) を使って $O(N \log N)$ 時間で求まる。
$\dfrac{1}{1 - A(x)}$ の前 $N$ 項は [inv of FPS](#inv-log-exp-of-FPS) を使って $O(N \log N)$ 時間で求まる。
これを畳み込めば、$\dfrac{1 - (A(x))^K}{1 - A(x)}$ の前 $N$ 項は $O(N \log N)$ 時間で求まる。
## $[x^K]\frac{P(x)}{Q(x)}$ を求める
### 行列累乗
長さ $N$ の数列 $\displaystyle P(x) = \sum_{n=0}^{N-1} P_nx^n$ と長さ $N + 1$ の数列 $\displaystyle Q(x) = \sum_{n=0}^{N} Q_nx^n$ に対して、$[x^K]\dfrac{P(x)}{Q(x)}$ は $O(N^3 \log K)$ 時間で求められる。
前 $N$ 項を求めておき、分母を線形漸化式に変換して、$1$ 要素シフトする行列を作り、行列累乗をすればよい。
#### 例
$[x^K]\dfrac{1}{1-ax-bx^2}$ を求める。
分母が $1 - ax - bx^2$ $\iff$ 線形漸化式 $A_n = aA_{n-1} + bA_{n-2}$ であるから、
$$
\begin{bmatrix}
A_{n-2} & A_{n-1}
\end{bmatrix}\begin{bmatrix}
0 & b\\
1 & a\\
\end{bmatrix} = \begin{bmatrix}
A_{n-1} & A_{n}
\end{bmatrix}
$$
が成り立ち、
$$
\begin{bmatrix}
1 & a
\end{bmatrix}\begin{bmatrix}
0 & b\\
1 & a\\
\end{bmatrix}^n = \begin{bmatrix}
A_{n} & A_{n+1}
\end{bmatrix}
$$
である。これは行列累乗で $O(\log K)$ 時間で計算できる。
### 高速きたまさ法 (Feduccia's algorithm)、$Q(x)Q(-x)$ (Bostan–Mori algorithm)
↑ は $O(N \log N \log K)$ 時間で計算できる。
詳しくは [線形漸化式の高速計算 | Nyaan’s Library](https://nyaannyaan.github.io/library/fps/kitamasa.hpp.html) などを参照
### 演習
今なら [aising2020 F - Two Snuke](https://atcoder.jp/contests/aising2020/tasks/aising2020_f) が解けるはず…！
11. $0 ≤ s_1 < s_2,\ s_1 + s_2 = n$ を満たす整数の組 $(s_1, s_2)$ 全てについて $(s_2 - s_1)$ を合計したものを $F_n$ とする。$(F_0, F_1, …, F_6)$ を求めよ。
12. 母関数 $F(x)$ を求めよ。(ヒント : <span style="color:white">階差を取ってみよう</span>)
13. [元の問題](https://atcoder.jp/contests/aising2020/tasks/aising2020_f) の答えを $[x^N]f(x)$ の形式で表せ。
14. どれくらいの時間計算量で解けるか？
## おまけ
### [オンライン整数列大辞典](https://oeis.org)
有名な整数列がたくさん載っている辞典。母関数がわからないとき、一般項がわからないとき、ここで調べるとみつかるかも？
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 マージテク
$M$ 個の多項式 $f_1, …, f_M$ があり、次数の合計が $\displaystyle\sum_{i=1}^M\deg(f_i) = N$ であるとき、総積の係数 $\displaystyle\prod_{i=1}^Mf_i(x) = \sum_{n=0}^NA_nx^n$ は $O(N \log N \log M)$ で求められる。
- $M$ 個の多項式のうち最も次数の小さなもの $2$ 個を掛けることを繰り返す (priority_queue で管理)
- $M$ 個の多項式のうち最も古いもの $2$ 個を掛けることを繰り返す (deque で管理)
などをするとできる。
#### 実装
```python=
F = deque([f_1, …, f_M])
while len(F) > 1:
a = F.popleft()
b = F.popleft()
F.append(convolution(a, b))
```
#### 例
> 長さ $N$ の数列 $A = (A_1, …, A_N)$ がある。
> 数列 $X = (X_1, …, X_{|X|})$ に対して、その **うれしさ** を総積 $\displaystyle\prod_{i=1}^{|X|}X_i$ で定義する。
> 数列 $A$ の部分列のうち長さが $M$ であるもの全てに対してうれしさを計算し、その総和を求めよ。
$$
[x^M]\left(\prod_{i=1}^N1 + A_ix\right)
$$
は $O(N (\log N)^2)$ で求められる。
### exp-log
数列 $\displaystyle A(x) = \sum_{n=0}^\infty A_nx^n$ に対して、$\displaystyle\prod_{k=1}^M A(x^k)$ の前 $N$ 項は $O(N (\log N + \log M))$ 時間で求められる。
#### 問題
$1$ から $N$ までの [分割数](https://ja.wikipedia.org/wiki/%E5%88%86%E5%89%B2%E6%95%B0) を $O(N \log N)$ 時間で求めよ。
#### 解答
分割数は以下の問題と同じである。
> (互いに区別できない) $1$ 円硬貨を無限枚、$2$ 円硬貨を無限枚、$3$ 円硬貨を無限枚、$4$ 円硬貨を無限枚、……
> 持っているとき、$n$ 円を支払う方法は何通りか？
$m$ 円硬貨のみを用いて $n$ 円を支払う方法の数の母関数は $\dfrac{1}{1 - x^m}$
$N$ 円より大きな硬貨には意味がないから、分割数の母関数は $\displaystyle\prod_{m=1}^N\frac{1}{1 - x^m}$ である。
ここで、$\displaystyle L(x) = \log\left(\frac{1}{1-x}\right) = \sum_{n=0}^\infty L_nx^n$ とおくと、
$$
\begin{aligned}
\prod_{m=1}^N\frac{1}{1 - x^m} &= \exp\left(\sum_{m=1}^N\log\left(\frac{1}{1-x^m}\right)\right)\\
&= \exp\left(\sum_{m=1}^N L(x^m)\right)\\
\end{aligned}
$$
$\exp$ は $O(N \log N)$ 時間で計算できるから、$\displaystyle \sum_{m=1}^N L(x^m)$ の前 $N + 1$ 項が計算できれば良い。
$$
L(x) = -\log(1 - x) = \sum_{n=1}^\infty \frac{x^n}{n}
$$
より、$L_n = \dfrac1n$ がわかる。( $O(N \log N)$ 時間かけて $L(x)$ の前 $N+1$ 項を計算しても良い。)
$$
L(x^m) = \sum_{n=0}^\infty L_nx^{mn}
$$
であるから、$L(x^m)$ の前 $N+1$ 項のうちに非 $0$ の項は高々 $1 + \dfrac Nm$ 個しか存在しない。
したがって、調和級数を考えれば $\displaystyle \sum_{m=1}^N L(x^m)$ は $O(N \log N)$ 時間で求められる。
### [[多項式・形式的べき級数] 高速に計算できるものたち | maspyのHP](https://maspypy.com/%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%83%BB%E5%BD%A2%E5%BC%8F%E7%9A%84%E3%81%B9%E3%81%8D%E7%B4%9A%E6%95%B0-%E9%AB%98%E9%80%9F%E3%81%AB%E8%A8%88%E7%AE%97%E3%81%A7%E3%81%8D%E3%82%8B%E3%82%82%E3%81%AE)
他にも書こうとしたけど、ここに網羅されてたのでここを見ましょう
Sign in with Wallet
Connect another wallet