1. 概要

本講座では，数列から定数係数線形漸化式を復元する問題について解説します．

例えば，Fibonacci 数列の先頭項

$$ S=(0,1,1,2,3,5,8,13) $$

を入力として，この数列が満たす漸化式

$$ S _ i = S _ {i-1} + S _ {i-2} $$

を出力するような問題を考えます．より正確には，有限数列が与えられたとき，その列と矛盾しない定数係数線形漸化式のうち，位数が最小のものを求める問題を扱います．この問題を，本講座では復元問題と呼びます．

復元問題を解く代表的なアルゴリズムが Berlekamp–Massey アルゴリズムです．Berlekamp–Massey アルゴリズムは，入力列を先頭から順に処理し，各時点で数列が満たす最小位数の漸化式を更新していくアルゴリズムです．

競技プログラミングでは，Berlekamp–Massey アルゴリズムは，しばしば Bostan–Mori のアルゴリズム（または Fiduccia のアルゴリズム）と組み合わせて用いられます．具体的には，求めたい無限数列の先頭項を十分多く計算し，Berlekamp–Massey アルゴリズムで線形漸化式を復元し，Bostan–Mori のアルゴリズムで第 $K$ 項を高速に求める，という流れです．この方法は BMBM 法と呼ばれることもあります．BMBM 法は考察や実装を簡略化できるだけでなく，計算量の改善につながることもあり，競技プログラミングでも重要な手法です．この方法を理解し実践できるようになることが，本講座の主目標となるでしょう．

6 節では補足として，Euclid の互除法を用いた復元問題の別解法を紹介します．このアルゴリズムは一見すると Berlekamp–Massey アルゴリズムとはかなり違う見た目をしていますが，詳しく分析すると，Berlekamp–Massey アルゴリズムの計算と対応するものとして解釈することもできます．Euclid の互除法による見方は，Half-GCD による高速化につながるなどの利点もあります．

2. 前提知識

次の講座の内容を理解していることを前提とします．

また，加えて本講座で用いる多項式に関する用語についてここで簡単に補足します．

多項式 $f(x)$ の次数を $\deg f(x)$ と書きます．$f(x)=0$ の場合には $\deg 0=-\infty$ と定義します．

多項式 $f(x)$ の最高次の係数が $1$ であるとき $f(x)$ はモニックであるといいます．

多項式 $f(x), g(x)$ について少なくとも一方が $0$ でないとき，$f(x), g(x)$ を共に割り切る多項式であって，次数最大かつモニックであるものを $\gcd(f(x),g(x))$ と書きます．この多項式は通常の Euclid の互除法と同様に計算できます．$\gcd(f(x),g(x))=1$ であるような $f(x),g(x)$ は互いに素であるといいます．

3. 問題設定

これまでの講座

では，数列の要素や多項式の係数は，単位的可換環 $R$ の元であるとしてきました．

本講座では $R$ は体であるとします．競技プログラミングでは，$R=\mathbb{Q}$（有理数全体）または $R=\mathbb{F}_p$ の場合（整数を素数 $p$ を法として考える場合）を想定してよいでしょう．

また計算量について述べるときは，$R$ 上の四則演算の回数を数えることにします．

3.1. 線形漸化式の復元問題

本講座では，次の問題を解くことを目標とします．

漸化式による定式化

【問題 1】

長さ $N$ の数列 $S=(S_0,S_1,\ldots,S_{N-1})$ が与えられます．$S$ と矛盾しない定数係数線形漸化式であって，位数が最小のものをひとつ出力してください．

つまり，位数 $L$ の定数係数線形漸化式

$$ S_i = c_1 S_{i-1} + c_2 S_{i-2} + \cdots + c_L S_{i-L} $$

が任意の $L\leq i < N$ について成り立つものであって，$L$ が最小のものをひとつ出力してください．

多項式による言い換え

線形漸化的数列と，有理式で表される形式的べき級数の対応を思い出せば，この問題は次のように言い換えることができます．

【問題 2】

$N-1$ 次以下の多項式

$$ S(x) = S_0 + S_1 x + \cdots + S_{N-1} x ^ {N-1} $$

が与えられます．非負整数 $L$ および $L$ 次以下の多項式 $Q(x)$ （ただし $[x ^ 0] Q(x) = 1$）であって，

$$ [x ^ i] Q(x) S(x) = 0\qquad (L\leq i < N) $$

が成り立つものを考えます．そのような組 $(L, Q(x))$ のうち，$L$ が最小であるものをひとつ出力してください．

有理式による言い換え

条件

$$ [x ^ i] Q(x) S(x) = 0\qquad (L\leq i < N) $$

は，$P(x) = Q(x)S(x)\bmod x ^ L$ を用いて

$$ Q(x) S(x) \equiv P(x)\pmod{x ^ N} $$

または $[x ^ 0]Q(x)=1$ に注意して

$$ S(x) \equiv \dfrac{P(x)}{Q(x)}\pmod{x ^ N} $$

と表すこともできます．したがって，【問題 2】は

$[x ^ 0]Q(x)=1$, $\deg Q(x)\leq L$,
$\deg P(x)\leq L-1$,
$S(x)\equiv \dfrac{P(x)}{Q(x)} \pmod{x ^ N}$

を満たすように $P(x), Q(x), L$ をとり，$L$ を最小化する問題と言い換えることもできます．また $L$ が最小である場合には

$$L = \max(\deg P(x) + 1, \deg Q(x))$$

が成り立ちます．

以下では，本節で述べた問題を，どの定式化であるかを区別せずに，単に復元問題と呼ぶことにします．

3.2. 入出力例

いくつかの例を通して，想定されている入出力がどのようなものかを簡単に確認します．先に本節で扱う入力列を挙げるので，解説に入る前にどのような出力になるのか考えてみてもよいでしょう．

$S=(1,2,4,8,16,32,64)$
$S=(64,32,16,8,4,2,1)$
$S=(0,1,1,2,3,5,8,13,21,34)$
$S=(0,1,4,9,16,25,36,49)$
$S=(10,1,1,2,3,5,8,13,21,34)$
$S=(1,0,0,0,0)$
$S=(0,0,0,0,0)$
$S=(1,2,4,7)$
$S=(0,0,0,0,1)$

なお，以下で解説する出力が復元問題の条件を満たすこと，特に $L$ の最小性について，ここで完全に証明することはしません．また証明なしに，解の一意性について言及する場合もあります．これらについては，後述の【定理 4】により確かめることもできます．

本節の例において，係数環 $R$ は $\mathbb{Q}$ （有理数全体）であるとします．