概要
以前に書いた記事
[数学] 形式的べき級数による数え上げ（AtCoder JSC2019予選問題F）
において、類題として並べた問題の1つを解説していきます。上記の記事の内容の大部分を仮定します。
問題を整理しておきます。以下、フィボナッチ数列を
\[F_0,F_1,F_2,F_3,\ldots = 0,1,1,2,\ldots\] と記号 $\{F_n\}$ で表します。
・$d_1 = F$ とする。
・$d_{i-1}$ の累積和を $d_i$ とすることで数列の列 $d_1,d_2,\ldots$ を定める。
・$d_{N,M}$ を求めよ。制約：$N\leqq 2\cdot 10^5$, $M\leqq 10^{18}$。
形式的べき級数の問題に読み替えると以下の通りです。
・$f(T) = \sum_{n=0}^{\infty}F_nT^n$ とする。
・$\frac{f(T)}{(1-T)^{N}}$ の $T^M$ の係数を求めよ。
あ、少し嘘で、$\frac{f(T)}{(1-T)^{N-1}}$ が正しいですが、いちいち $N-1$ にするのが邪魔なので、これで行きます。実装するときには適切に 1 ずらしてください。
計算すべき $M$ が最大 $10^{18}$ とかなり大きいですね。
線形漸化式と形式的べき級数
Fibonacci数列の母関数
Fibonacci数列は、
\[\begin{cases}F_0 = 0, F_1 = 1\\n\geq 0\implies F_{n+2} – F_{n+1} – F_n = 0\end{cases}\]
の2条件により定まるのでした。$n$ の範囲などは省略されることが多いですが、きちんと書いておきます。
$f(T) = F_0+F_1T+F_2T^2+\cdots$ とします。$n\geq 0$として、$(1-T-T^2)f(T)$ の $n+2$ 次の項を計算してみます。積が $n+2$ 次になる項の組み合わせを考えると、次の3つの和であることが分かります。
・左側のカッコから $1$ を選び出した場合：$1\cdot F_{n+2}T^{n+2}$.
・左側のカッコから $-T$ を選び出した場合：$(-T)\cdot F_{n+1}T^{n+1}$.
・左側のカッコから $-T^2$ を選び出した場合：$(-T^2)\cdot F_{n}T^{n}$.
よってこの係数は $F_{n+2} – F_{n+1} – F_n$ となりますが、漸化式よりこれは $0$ に等しいです。
【分かったこと】$n\geq 0$ に対して、$(1-T-T^2)f(T)$ の $T^{n+2}$ の係数は $0$ に等しい。
うっかり $(1-T-T^2)f(T) = 0$ を結論付けたくなるところではありますが、$n\geq 0$ に注意すると次の通りです。
【分かったこと】$(1-T-T^2)f(T)$ は1次以下の多項式。したがって、ある定数 $a,b$ に対して $f(T) = \frac{a+bT}{1-T-T^2}$ が成り立つ。
$a,b$ の計算も簡単です。未使用の条件 $F_0=0$, $F_1=1$ を使うと
\[(1-T-T^2)f(T) = (1-T-T^2)(0+T+\cdots) = (1-T)T + \text{(2次以上)} = T + \text{(2次以上)}\] となるので、Fibonacci数列の母関数が $f(T) = \frac{T}{1-T-T^2}$ と決定できました。
線形漸化式と形式的べき級数
定数 $c_1,\ldots,c_k$ を用いて
\[n\geq 0\implies a_{n+k} + c_1a_{n+k-1} +\cdots + c_ka_n = 0\] と表せる漸化式を、線形漸化式と言います（「定係数斉次線形漸化式」くらい修飾語がつくこともありますが、本記事では簡略化しています）。このとき上述と同様の議論により、数列 $\{a_n\}$ の母関数は $\frac{\text{$k-1$ 次以下の多項式}}{1+c_1T+\cdots+c_kT^k}$ と表せることが分かります。この対応は同値で、
線形漸化式を持つ $\iff$ 分子の方が次数が低い有理式を母関数に持つ
ということが成り立ちます。
部分分数分解（関連する応用等）
部分分数分解
有理式について良い理解を手に入れれば、線形漸化式を持つ数列について良い理解が得られることが期待されます。有理式の扱いにおいて、次が基本的です：
【部分分数分解】有理式 $\frac{p(T)}{q(T)}$ において、$p$ の次数が $q$ の次数よりも小さくて、$q(T) = \prod (1-\alpha_iT)^{m_i}$ と因数分解されるとき、$\frac{p(T)}{q(T)} = \sum_{1\leq d_i\leq m_i} \frac{c_{i,d_i}}{(1-\alpha_iT)^{d_i}}$ となる定数 $c_{i,d_i}$ が存在する。
記号が分かりにくいですが、例えば
\[\frac{p(T)}{(1-T)(1-2T)^2(1-3T)^3} = \frac{c_{1,1}}{1-T} + \frac{c_{2,1}}{1-2T} + \frac{c_{2,2}}{(1-2T)^2} + \frac{c_{3,1}}{1-3T} + \frac{c_{3,2}}{(1-3T)^2} + \frac{c_{3,3}}{(1-3T)^3}\] といった要領です。高校数学でも積分計算などで利用されます。なお、分母の多項式は、複素数範囲において必ず 1 次式の積に分解できるので、このような表示は常に可能だということになります。
有理式 $\frac{1}{(1-\alpha T)^d}$ について
ちょっと脱線していきます。
部分分数分解のパーツである $\frac{1}{(1-\alpha)^d}$ と、形式的べき級数の関係を確認しておきます。過去記事で述べたように、$\frac{1}{(1-T)^d} = \sum_{n=0}^{\infty}\binom{n+d-1}{d-1}T^n$ が成り立つのでした。$T$ を $\alpha T$ に置き換えて、
\[\frac{1}{(1-\alpha T)^d} = \sum_{n=0}^{\infty}\binom{n+d-1}{d-1}\alpha^{n}T^n\] となることが分かります。
$T^n$ の係数が、($n$ の $d-1$ 次多項式) $\cdot \alpha^n$ となっていますね。
応用例
例えば Fibonacci 数列の母関数は、$\alpha,\beta = \frac{1\pm \sqrt{5}}{2}$ を用いて、$\frac{T}{(1-\alpha T)(1-\beta T)}$ と表せます。これを部分分数分解すると、ある定数 $c_0,c_1$ に対して $f(T) = \frac{c_0}{1-\alpha T} + \frac{c_1}{1-\beta T}$ と書けるので、Fibonacci数列の一般項は $F_n = c_0\alpha^n + c_1\beta^n$ と表せることが分かります。
有理式の計算を詰める、あるいは、$F_0,F_1$ の値から逆算すると$c_0,c_1$ が求まって、有名な式 $F_n = \frac{\alpha^n-\beta^n}{\alpha-\beta}$ を導くことができます（この明示公式は無理数を含むため、競プロでは扱いにくいように感じるかもしれませんが、$\alpha$ や $\beta$ は $\alpha^2=\alpha+1$ という計算規則を満たす何かだとだけ思っていれば、自然に代数的に取り扱えます。代数的整数論を多少知っていると、modの取り扱いも容易）。
少し一般化すると
数列 $\{a_n\}$ が線形漸化式を持つ $\iff$ $a_n$は$n^k\alpha^n$ の形の数列の線形結合である
という同値性を証明することもできます。
部分分数分解は数列の和の計算にも便利です。例えば 数列 $\{2^n\}$ の累積和を考えることは、$\frac{1}{(1-2T)(1-T)}$ の係数を考えることと等価です。この有理式は $\frac{2}{1-2T} – \frac{1}{1-T}$ と部分分数分解できるので，$\sum_{k=0}^n2^k = 2\cdot 2^n-1$ となることが分かります。
本問題の場合
本問題に戻ります。Fibonacci数列の母関数が $\frac{T}{1-T-T^2}$ でしたから、その $N$ 回累積和の母関数は $\frac{T}{(1-T)^{N}(1-T-T^2)}$ です。これは次のように部分分数分解できます。
\[\frac{T}{(1-T)^N(1-T-T^2)} = \frac{c_N}{(1-T)^N}+\cdots+\frac{c_1}{1-T}+\frac{p+qT}{1-T-T^2}\]
上で紹介した形と違っていますが、$1-T-T^2 = (1-\alpha T)(1 – \beta T)$ と分解したときの$\frac{1}{1-\alpha T}$, $\frac{1}{1-\beta T}$ の線形結合をまとめて書いています。係数の具体値を求めていきましょう。
この部分分数分解の等式は、もはや形式的べき級数というよりも有理式の等式です。したがって、割と好き勝手に扱って良いです。$1-T$ がたくさん出てくるので、変数変換 $S = 1-T$ を利用します：
\[\frac{-1+S}{S^N(1-3S+S^2)} = \frac{c_N}{S^N}+\cdots+\frac{c_1}{S}+\frac{-(p+q)+qS}{1-3S+S^2}.\]
この係数は次のようにして計算できます。まず、$\frac{-1+S}{1-3S+S^2}$ を $S$ の形式的べき級数にします：
\[
\frac{-1+S}{1-3S+S^2} = b_0+b_1S+b_2S^2+b_3S^3+\cdots.
\]
この $\{b_n\}$ は、漸化式 $n\geq0\implies b_{n+2} – 3b_{n+1} + b_n = 0$ を利用すれば順に計算していくことができます。この式を $S^N$ で割れば、
\[ \frac{-1+S}{S^N(1-3S+S^2)} = \frac{b_0}{S^N}+\cdots+\frac{b_{N-1}}{S}+\bigl(b_N+b_{N+1}S+b_{N+2}S^2+\cdots\bigr)\] となりますが、$b$ の $N$ 番目以降についてもやはり同じ漸化式 $n\geq 0\implies b_{N+n+2} – 3b_{N+n+1} + b_{N+n} = 0$ は成り立ちますから，
\[b_N+b_{N+1}S+b_{N+2}S^2+\cdots = \frac{b_N+(b_{N+1}-3b_N)S}{1-3S+S^2}\] です。したがって
\[ \frac{-1+S}{S^N(1-3S+S^2)} = \frac{b_0}{S^N}+\cdots+\frac{b_{N-1}}{S}+\frac{b_N+(b_{N+1}-3b_N)S}{1-3S+S^2}\] と部分分数分解の係数が求まりました。
まとめ（実装用）
・$\frac{-1+S}{1-3S+S^2} = b_0+b_1S+b_2S^2+b_3S^3+\cdots$ の係数を $N+1$ 次まで計算しておく。漸化式 $b_0 = -1, b_1 = -2, b_{n+2} – 3b_{n+1}+b_n=0$ を利用して $N$ 回計算すればよい。
・$c_N = b_0,\ldots,c_1 = b_{N-1}$ とおく。$p=2b_N-b_{N+1}$, $q = b_{N+1}-3b_N$ とおく。
・答は $\frac{c_N}{(1-T)^N}+\cdots+\frac{c_1}{1-T}+\frac{p+qT}{1-T-T^2}$ の $T^M$ の係数である。したがって、$\sum_{i=1}^{N} c_i\binom{M+i-1}{i-1} + pF_{M+1} + qF_M$ が答である。
参考
実は今回の問題では、最終的な式をもっときれいにすることが可能です。実は $b_n = -F_{2n+1}$ が成り立って、色々な登場人物が Fibonacci 数列の直接の関係者になってしまいます。
・$c_i = -F_{2N-2i+1}$.
・$p = F_{2N}$, $q = F_{2N-1}$.
・$pF_{M+1} + qF_M = F_{M+2N}$.
結論の式が $-\sum_{i=1}^{N} F_{2N-2i+1}\binom{M+i-1}{i-1} + F_{M+2N}$ くらいまで整理されます。
しかしこの部分については形式的べき級数や有理式に一般に適用できる現象ではなくて、Fibonacci固有の幸運なので、あまり気にしないで良いかと思います。
今回 $b_n$ が $F_{2n}$ 的なもので表せたのは、形式的べき級数の分母に次の関係があるからです：
\[1-T-T^2 = (1-\alpha T)(1-\beta T) \implies 1-3S+S^2 = (1-\alpha^2S)(1-\beta^2S).\]
これが成り立つ時点で、数列 $\{b_n\}$ の一般項は $\alpha^{2n}, \beta^{2n}$ の線形結合となって、$F_{2n}$ の関係者っぽいです（「$F_{2n}$と$F_{2n+1}$ の線形結合」あるいは「$F_{2n}$と$L_{2n}$（Lucas数列）の線形結合」などと断定できる）。
この分母は、$S = 1-T$ という変数変換により得られるものでした。多項式の零点の対応を考えると、$1 – \frac{1}{\alpha} = \frac{1}{\alpha^2}$ というところに原因があると言えて、Fibonacci数列に特化してピンポイントに成り立った幸運です。
一般に線形漸化式で定まる数列から、今回のように累積和の部分分数分解の係数 $b_n$ を計算したとしても、自身の数列の項を使って表せるわけではありません。したがって、この部分については形式的べき級数や有理式に一般に適用できる現象ではありません。
