1. 概要

本講座では，正整数 $\boldsymbol{m}$ を法とする線形漸化式の復元問題を扱います．

線形漸化式の復元では，数列から定数係数線形漸化式を復元する問題を，係数環が体である場合に解説しました．その場合のアルゴリズムの代表が Berlekamp–Massey アルゴリズムです．Berlekamp–Massey アルゴリズムは，入力列を先頭から順に処理し，各時点で数列が満たす最小位数の漸化式を更新していくアルゴリズムです．

一方で，競技プログラミングでもしばしば $\mathbb Z/m\mathbb Z$ を係数環として数列を扱います．$m$ が素数であればこれは体ですが，$m$ が合成数である場合には体ではありません．このとき，Berlekamp–Massey アルゴリズムをそのまま用いることはできません．アルゴリズムは $0$ でない元による除算ができることを仮定しているからです．

そこで係数環が $\mathbb Z/m\mathbb Z$ の場合に線形漸化式の復元問題を解くのが Reeds–Sloane アルゴリズムです．本講座では，Reeds–Sloane アルゴリズムを解説します．

2. 前提知識

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

3. $m$ を法とする復元問題

3.1. 問題

$m$ を正整数とします．

本講座で扱う復元問題は，線形漸化式の復元【問題 2】を環 $\mathbb{Z}/m\mathbb{Z}$ で考えるものです．

【復元問題】

$N-1$ 次以下の $\mathbb{Z}/m\mathbb{Z}$ 係数多項式

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

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

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

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

なお，$L=N$, $Q(x)=1$ とすれば組 $(L,Q(x))$ は復元問題の条件

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

を満たします．$L\leq i < N$ を満たす $i$ が存在しないからです．したがって復元問題の解は必ず存在します．

また，$P(x) = Q(x)S(x)\bmod x ^ L$ とすることで，復元問題をしばしば

$[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}$

となる組 $(L,Q(x),P(x))$ を求める問題として扱います．ここで $\dfrac{P(x)}{Q(x)}$ は，形式的べき級数環における商，つまり $P(x)\cdot Q(x) ^ {-1}$ を表します．$[x ^ 0]Q(x)=1$ であるため，$Q(x)$ は形式的べき級数環において乗法逆元を持ちます．この事実は，係数環が体でなく，一般の単位的可換環である場合にも成り立ちます．

3.2. 体の場合との違い

$m$ が合成数であるとき，$\mathbb{Z}/m\mathbb{Z}$ は体ではありません．このことが，体の場合，つまり

線形漸化式の復元

の場合とどのような違いを生じるのかを確認します．

まず，Berlekamp–Massey アルゴリズムの更新式は，典型的には

$$Q _ {\mathrm{new}}(x) = Q(x) - \frac{\Delta}{b}x ^ {n-n_0}B(x)$$

という形をしています．つまり $0$ でない元 $b$ による除算が用いられます．このため，体上では $b\ne0$ ならば必ず $b$ で割ることができます．しかし，$\mathbb Z/m\mathbb Z$ で $m$ が合成数である場合には，$b\ne0$ であっても $b$ が逆元を持つとは限りません．したがって，Berlekamp–Massey アルゴリズムを適用できません．

また，復元問題の解の構造にも違いが生じます．例えば，$2L\leq N$ の場合の解の一意性（線形漸化式の復元【定理 4】）は $\mathbb{Z}/m\mathbb{Z}$ の場合には成り立ちません．$L$ が $N$ に比べて非常に小さい場合でも，解が複数存在する場合があります．例えば

$$ m=4,\qquad S = (2,2,2,2,2,2,2,2) $$

とするとき，この数列は $2$ 通りの最小位数の定数係数線形漸化式

$$ \begin{aligned} S _ i &= S _ {i-1},\qquad (i\geq 1) \\ S _ i &= 3S _ {i-1},\qquad (i\geq 1) \\ \end{aligned} $$

を満たします．【復元問題】の形でいえば，$(L,Q(x))$ として複数の解

$$ (1,1-x), \qquad (1,1-3x) $$

をとることができます．

線形漸化式の復元【定理 4】の証明については，多項式の $\gcd$ や互いに素の性質を用いている部分が，係数環が体であることを用いている部分になります．$\mathbb{Z}/m\mathbb{Z}$ では，多項式の除法（素数を法とする多項式【定義 1】）や $\gcd$ の定義・性質を体の場合と同じようには扱えません．このように，多項式の除法に基づいた議論には注意が必要です．

3.3. 解の一意性について

競技プログラミングにおける復元問題の利用方法として最も典型的なものは，無限数列の先頭項から数列が満たす漸化式を予測し，その漸化式を元に第 $K$ 項を求めるというものです（線形漸化式の復元第 5 節）．

一方で上で見たように，$\mathbb{Z}/m\mathbb{Z}$ 上の復元問題では，$L$ が $N$ に比べて非常に小さい場合であっても解の一意性が成り立たない場合があります．このことは一見すると，応用上の問題になりそうです．いくら先頭項を集めて漸化式を予測しても複数の漸化式が条件を満たしてしまうと，どの漸化式を仮定すればよいのかが定まらないからです．

しかし，次の定理の形での一意性は成り立つため，漸化式が一意に定まらなくとも，数列の第 $K$ 項を求める状況では問題になりません．

【定理 1】

この定理において，$R$ を単位的可換環とし，多項式や形式的べき級数の係数は $R$ の元であるとする．

$S(x)$ を $N-1$ 次以下の多項式とする．$L$ を $2L\leq N$ を満たす非負整数とし，多項式 $P_1(x), Q_1(x), P_2(x), Q_2(x)$ が以下を満たすとする．

$$ \begin{aligned} &\deg P_i(x)\leq L-1,\qquad \deg Q_i(x)\leq L\qquad (i=1,2),\\\ &[x ^ 0] Q_i(x) = 1\qquad (i=1,2),\\\ &S(x) \equiv \frac{P_1(x)}{Q_1(x)}\equiv \frac{P_2(x)}{Q_2(x)} \pmod{x ^ N}. \end{aligned} $$

このとき形式的べき級数の等式

$$ \frac{P_1(x)}{Q_1(x)}= \frac{P_2(x)}{Q_2(x)} $$

が成り立つ．

定理の主張および以下の証明の理解において，$[x ^ 0]Q _ i(x)=1$ より $Q _ i(x)$ が形式的べき級数逆元を持つことに注意してください．これは係数環が体であるという仮定なしに成り立ちます．

仮定より

$$\frac{P_1(x)}{Q_1(x)}\equiv \frac{P_2(x)}{Q_2(x)} \pmod{x ^ N}$$

が成り立ちます．両辺の $Q_1(x)Q_2(x)$ 倍から，

$$P_1(x)Q_2(x)\equiv P_2(x)Q_1(x) \pmod{x ^ N}$$

となります．この両辺の次数は $2L-1$ 以下です．このことと $2L\leq N$ より上の合同式は実際には等式で，

$$P_1(x)Q_2(x) = P_2(x)Q_1(x)$$

が成り立ちます．この両辺に，形式的べき級数 $\dfrac{1}{Q_1(x)Q_2(x)}$ をかけることで

$$ \frac{P_1(x)}{Q_1(x)}= \frac{P_2(x)}{Q_2(x)} $$

が分かります．$\blacksquare$

この定理より，たとえ復元問題の解として得られる $Q(x)$ が一意でなくても，$2L\leq N$ が成り立つ範囲では，それらが表す形式的べき級数は一意に定まります．したがって，復元したどの漸化式を用いて第 $K$ 項を求めても，同じ値が得られます．

一方で，$2L>N$ の場合にはこの一意性は保証されません．これは体上の Berlekamp–Massey アルゴリズムを用いる場合と同様に，復元結果を無限数列の予測として利用する際には注意すべき点です．

4. Reeds–Sloane アルゴリズム

4.1. 素数べきへの帰着

本節において，簡単のため $m>1$ を仮定します．$m=1$ の場合は自明です．

$m$ の素因数分解を

$$ m=\prod_{0\leq j<k}p_j^{e_j} $$

とします．以下では，同じ多項式 $S(x)$ に対する復元問題を，$m$ や $p_j^{e_j}$ を法として考えます．

$m$ を法とする復元問題の解のひとつを $(L,Q(x))$，$p_j^{e_j}$ を法とする復元問題の解のひとつを $(L_j,Q_j(x))$ とします．

まず，$m$ を法とする解 $(L,Q(x))$ を係数ごとに $p_j^{e_j}$ を法として見ると，$p_j^{e_j}$ を法とする復元問題について，最小性以外の条件を満たします．したがって各 $j$ について $L_j\leq L$ が成り立ちます．

逆に，素数べき法ごとの解から，$m$ を法とする解を構成できます．

$$ \widetilde L=\max_{0\leq j<k}L_j $$

とします．中国剰余定理により，$\mathbb Z/m\mathbb Z$ 係数多項式 $\widetilde Q(x)$ を

$$ [x ^ i]\widetilde Q(x)\equiv [x ^ i]Q_j(x)\pmod{p _ j ^ {e _ j}} \qquad (0\leq i\leq \widetilde L,\ 0\leq j<k) $$

が成り立つようにとります．このとき $(\widetilde L,\widetilde Q(x))$ は，$m$ を法とする復元問題について，最小性以外の条件を満たします．一方で上で見たように $L_j\leq L$ がすべての $j$ について成り立つため，$\widetilde L\leq L$ です．$L$ は $m$ を法とする復元問題の最小値だったので，$L=\widetilde L$ が従います．

したがって，$m$ を法とする復元問題を解くには，次のようにすればよいです．

各素数べき $p_j^{e_j}$ を法として，復元問題の解 $(L_j,Q_j(x))$ を求める．
$L=\max_j L_j$ とする．
中国剰余定理により，係数ごとに $[x ^ i]Q(x)\equiv [x ^ i] Q_j(x)\pmod{p_j^{e_j}}$ を満たす $L$ 次以下の多項式 $Q(x)$ を構成する．

このとき $(L,Q(x))$ が，$m$ を法とする復元問題の解になります．

4.2. 素数べきの場合の流れ

4.1 節により，$m$ を法とする復元問題は，素数べきの法での復元問題に帰着できることが分かりました．本節以降では $m$ が素数べき

$$ m=p ^ e $$

である場合を考えます．

Berlekamp–Massey アルゴリズムでは，数列の先頭項から順に処理していき，

その時点での最適解 $(L,Q(x))$ に加えて，
係数打ち消しのために用いる補助的なデータとして，前回 $L$ が更新されたときの情報

を管理するのでした．

Reeds–Sloane アルゴリズムでは，これと似たデータを $p$ 進付値ごとに管理します．より正確にはまず，各 $j=0,1,\ldots,e-1$ に対して，組 $(L_j, Q_j(x))$ であって

$$ \begin{aligned} &[x ^ 0]Q _ j(x)=p ^ j, \qquad \deg Q_j(x) \leq L_j,\\ &[x ^ i]Q _ j(x)S(x)=0\qquad (L_j\leq i < n) \end{aligned} $$

を満たすものを考えます．各 $n$ について $n$ 項処理した時点で，このような組 $(L_j,Q_j(x))$ であって $L_j$ が最小であるものを管理します．これらは元の復元問題を，定数項が $1$ という条件から，定数項が $p ^ j$ という条件に一般化したものです．

さらに係数打ち消しのために用いる補助的なデータとして，前回 $L_j$ が更新されたときの更新式に対応する情報

$$ B _ j(x),\qquad L _ {B,j},\qquad n _ {B,j},\qquad t _ {B,j} $$

を管理します．

より詳しいアルゴリズムの内容は，次節の疑似コードを参照してください．

4.3. 疑似コード

素数べき $p ^ e$ を法とする復元問題に対する Reeds–Sloane アルゴリズムの疑似コードは次のようになります．

Reeds_Sloane_Prime_Power(S, p, e):
  N := length(S)
  m := p^e

  for j = 0, 1, ..., e-1:
    Q[j](x) := p^j
    L[j] := 0
    n_B[j] := -1

  for n = 0, 1, ..., N-1:
    for j = 0, 1, ..., e-1:
      Delta[j] := [x^n] Q[j](x) S(x)
      write Delta[j] = t[j] p^u[j], where t[j] has a multiplicative inverse

    Q_new := Q
    L_new := L

    for j = 0, 1, ..., e-1:
      if u[j] = e:
        continue

      k := e - 1 - u[j]

      if n_B[k] = -1:
        Q_new[j](x) := Q[j](x)
        L_new[j] := n + 1
      else:
        c := t[j] / t_B[k]
        Q_new[j](x) := Q[j](x) - c x^(n-n_B[k]) B[k](x)
        L_new[j] := max(L[j], L_B[k] + n - n_B[k])

    for j = 0, 1, ..., e-1:
      if L[j] < L_new[j]:
        k := e - 1 - u[j]
        B[j](x) := Q[k](x)
        L_B[j] := L[k]
        n_B[j] := n
        t_B[j] := t[k]

    Q := Q_new
    L := L_new

  return (L[0], Q[0](x))

ここで初期化 $n_{B,j}=-1$ は，添字 $j$ に対応する補助データがまだ存在しないことを表します．

$t_j, u_j$ については $\Delta_j\ne0$ のときは

$$ \Delta_j = t _ j p ^ {u_j},\qquad t _ j\in(\mathbb{Z} / p ^ e\mathbb{Z}) ^ \times, 0\leq u_j < e $$

と書きます．$u _ j$ は $\Delta _j$ の $p$ 進付値です．また $\Delta_j=0$ の場合には，便宜上 $t_j=1, u_j=e$ とします．

$\Delta_j\ne0$ のとき，さらに $k=e-1-u_j$ で定まる添字 $k$ における補助データを用いて，$Q _ j(x)S(x)$ の $x ^ n$ 係数を打ち消します．この際に必要な除算は $c=\dfrac{t _ j}{t _ {B,k}}$ だけであり，$t_{B,k}$ は過去のある $t$ として保存されたものなので乗法逆元を持ちます．したがって，この除算は $\mathbb{Z} / p ^ e\mathbb{Z}$ 上で行うことができます．

4.4. 不変条件

この節では，疑似コードで管理しているデータが満たすべき性質を述べます．4.5 節以降で，これらの性質が実際に成り立つことを帰納法により証明します．

先頭 $n$ 項を処理した時点，つまり $S_0,S_1,\ldots,S_{n-1}$ までを処理した時点で，次の性質が成り立ちます．

まず，各 $j=0,1,\ldots,e-1$ について，組 $(L_j,Q_j(x))$ は

$$ \begin{aligned} &[x ^ 0]Q _ j(x)=p ^ j, \qquad \deg Q_j(x) \leq L_j,\\ &[x ^ i]Q _ j(x)S(x)=0\qquad (L_j\leq i < n) \end{aligned} $$

を満たします．さらに，このような組の中で $L_j$ は最小です．

次に，保存された補助データに関する性質を述べます．添字 $j$ に対応する補助データが存在しない，つまり $n_{B,j}=-1$ である場合には，

$$ L_j=0 $$

が成り立ちます．一方，添字 $j$ に対応する補助データ

$$ B _ j(x), \qquad L _ {B,j}, \qquad n _ {B,j}, \qquad t_{B,j} $$

が存在する場合には，

$$ \begin{aligned} &\deg B_j(x)\leq L_{B,j}, \\ &[x ^ i] B _ j(x) S(x) = 0\qquad (L _ {B,j}\leq i < n _ {B,j}), \\ &[x ^ {n _ {B,j}}]B _ j(x)S(x) = t _ {B,j}p ^ {e-1-j}, \\ &L _ j = n _ {B,j} + 1 - L _ {B,j} \end{aligned} $$

が成り立ちます．また，$t_{B,j}$ は $\mathbb{Z}/p ^ e\mathbb{Z}$ において乗法逆元を持ちます．

$n=0$ の場合，つまり初期化時点でこれらが成り立つことは容易に確認できます．以下では，$n$ 番目の係数を処理する更新によって，これらの性質が保たれることを確認します．

4.5. 係数条件の証明

以下では，先頭 $n$ 項を処理した時点で 4.4 節の不変条件が成り立っていると仮定し，$n$ 番目の係数を処理した後，つまり先頭 $n+1$ 項を処理した時点でも同じ不変条件が成り立つことを示します．まず，更新後の $(L_j,Q_j(x))$ が係数条件を満たすことを確認します．

先頭 $n$ 項を処理した時点で，

$$ [x ^ i]Q_j(x)S(x)=0\qquad (L_j\leq i<n) $$

が成り立っているとします．$n$ 番目の係数を $\Delta_j = [x ^ n]Q_j(x)S(x)$ とします．

4.5.1. $\Delta_j=0$ の場合

この場合，疑似コードでは $Q_j(x),L_j$ を更新しません．また

$$ [x ^ n]Q_j(x)S(x)=\Delta_j=0 $$

なので，

$$ [x ^ i]Q_j(x)S(x)=0\qquad (L_j\leq i<n+1) $$

が成り立ちます．したがって係数条件は保たれます．

4.5.2. 参照する補助データが存在しない場合

次に $\Delta_j\ne0$ とします．$\Delta_j=t_jp^{u_j}$ と書き，$k=e-1-u_j$ とします．

まず $n_{B,k}=-1$ の場合，添字 $k$ に対応する保存された補助データが存在しない場合を考えます．この場合の更新式は

$$ Q _ j ^ {\mathrm{new}}(x) = Q_j(x), \qquad L _ j ^ {\mathrm{new}}=n+1 $$

です．このとき $L_j^{\mathrm{new}}\leq i < n+1$ を満たす $i$ は存在しないため，

$$ [x ^ i]Q _ j ^ {\mathrm{new}}(x)S(x)=0\qquad (L_j ^ {\mathrm{new}}\leq i < n + 1) $$

は自動的に満たされます．また $Q_j(x)$ は変更していないので，

$$ [x ^ 0]Q_j ^ {\mathrm{new}}(x)=p ^ j $$

も保たれます．さらに $\deg Q_j(x)\leq L_j\leq n$ であるため，

$$ \deg Q_j^{\mathrm{new}}(x)\leq L_j^{\mathrm{new}} $$

も成り立ちます．

4.5.3. 保存された補助データを用いる場合

次に，添字 $k=e-1-u_j$ に対応する保存された補助データ

$$ B_k(x),\qquad L _ {B,k},\qquad n _ {B,k},\qquad t _ {B,k} $$

が存在する場合を考えます．この場合の更新式は

$$ \begin{aligned} Q_j ^ {\mathrm{new}}(x) &= Q_j(x) - \frac{t _ j}{t _ {B,k}}x ^ {n-n_{B,k}}B_k(x), \\ L_j ^ {\mathrm{new}} &= \max(L_j, L _ {B,k} + n - n _ {B,k}) \end{aligned} $$

となるのでした．

まず不変条件と $k=e-1-u_j$ より，

$$ [x ^ {n_{B,k}}]B_k(x)S(x) = t _ {B,k}p ^ {u_j} $$

が成り立ちます．したがって

$$ [x ^ n]x ^ {n-n_{B,k}}B_k(x)S(x) = t _ {B,k}p ^ {u_j} $$

となります．一方，$[x ^ n]Q_j(x)S(x)=\Delta_j=t _ j p ^ {u_j}$ なので，

$$ [x ^ n]Q_j ^ {\mathrm{new}}(x)S(x) = \Delta_j - \frac{t _ j}{t _ {B,k}}\cdot t _ {B,k}p ^ {u_j} = 0 $$

となります．

次に，$n$ より低い次数の係数に関する条件を確認します．不変条件より，

$$ [x ^ i]B_k(x)S(x)=0\qquad (L _ {B,k}\leq i < n _ {B,k}) $$

が成り立っています．したがって，シフト後の多項式について

$$ [x ^ i]x ^ {n-n _ {B,k}}B_k(x)S(x)=0 \qquad (L _ {B,k} + n - n _ {B,k}\leq i < n) $$

が成り立ちます．$L _ j$ に対する更新式より $L_j\leq L ^ {\mathrm{new}} _ j$，$L _ {B,k} + n - n _ {B,k} \leq L ^ {\mathrm{new}}_j$ が成り立つので，$L_j ^ {\mathrm{new}}\leq i < n$ の範囲では，$Q_j(x)S(x)$ の係数も，$x ^ {n-n _ {B,k}}B_k(x)S(x)$ の係数もともに $0$ です．よって

$$ [x ^ i]Q_j ^ {\mathrm{new}}(x)S(x)=0 \qquad (L_j ^ {\mathrm{new}}\leq i < n) $$

が成り立ちます．以上により

$$ [x ^ i]Q_j ^ {\mathrm{new}}(x)S(x)=0 \qquad (L_j ^ {\mathrm{new}}\leq i<n+1) $$

が示されました．

また，補助データは過去に保存されたものなので $n _ {B,k} < n$ です．よって $x ^ {n-n_{B,k}}B_k(x)$ は定数項を持たず，

$$ [x ^ 0]Q_j ^ {\mathrm{new}}(x)=p ^ j $$

も保たれます．さらに

$$ \deg Q_j(x)\leq L_j,\qquad \deg B_k(x)\leq L_{B,k} $$

より，

$$ \deg Q _ j ^ {\mathrm{new}}(x)\leq L _ j^{\mathrm{new}} $$

も成り立ちます．

以上で，更新後の $(L_j,Q_j(x))$ が係数条件を満たすことが分かりました．

4.6. 補題

$L_j$ の最小性および，補助データに関する不変条件の証明のために，補題を準備します．

【補題 2】

$L, M, n$ を非負整数，$A(x)$ を $L$ 次以下の多項式，$B(x)$ を $M$ 次以下の多項式とし，

$$ P_A(x):=A(x)S(x)\bmod x ^ L,\qquad P_B(x):=B(x)S(x)\bmod x ^ M $$

とおく．さらに定数 $a,b$ について

$$ \begin{aligned} A(x)S(x) - P_A(x) &\equiv a x ^ n \pmod{x ^ {n+1}}, \\\ B(x)S(x) - P_B(x) &\equiv b x ^ n \pmod{x ^ {n+1}} \end{aligned} $$

が成り立つとする．このとき $H(x)=B(x)P_A(x)-A(x)P_B(x)$ とおくと，次が成り立つ．

$$ \begin{aligned} &\deg H(x)\leq L+M-1, \\\ &[x ^ n]H(x) = b\cdot [x^0]A(x) - a\cdot [x^0]B(x) \end{aligned} $$

まず $\deg H(x)\leq L+M-1$ については，

$$ \deg A(x)\leq L, \deg P_A(x)\leq L-1,\qquad \deg B(x)\leq M, \deg P_B(x)\leq M-1 $$

より明らかです．$[x ^ n]H(x)$ については，

$$ \begin{aligned} H(x) &= B(x)P_A(x)-A(x)P_B(x) \\ &\equiv B(x)(A(x)S(x)-ax ^ n)-A(x)(B(x)S(x)-bx ^ n) \\ &\equiv bx ^ nA(x)-ax ^ nB(x) \pmod{x ^ {n+1}} \end{aligned} $$

から分かります．$\blacksquare$

【補題 3】

多項式 $R(x)$ と非負整数 $M,n,j$ （ただし $0\leq j\leq e-1$）および，乗法逆元を持つ $t$ が次を満たすとする．

$$ \begin{aligned} &\deg R(x)\leq M, \\\ &[x ^ i]R(x)S(x)=0\qquad (M\leq i < n), \\\ &[x ^ n]R(x)S(x)=tp ^ {e-1-j} \end{aligned} $$

このとき非負整数 $L$ および多項式 $Q(x)$ が

$$ \begin{aligned} &[x ^ 0]Q(x)=p^j,\qquad \deg Q(x)\leq L, \\\ &[x ^ i]Q(x)S(x)=0\qquad (L\leq i < n + 1) \end{aligned} $$

を満たすならば，$L\geq n+1-M$ が成り立つ．

【補題 2】を $A(x)=Q(x),B(x)=R(x)$ として適用します．仮定より

$$ P_A(x)=Q(x)S(x)\bmod x ^ L,\qquad P_B(x)=R(x)S(x)\bmod x ^ M $$

とすれば

$$ \begin{aligned} Q(x)S(x)-P_A(x)&\equiv 0 \pmod{x ^ {n+1}}, \\ R(x)S(x)-P_B(x)&\equiv tp ^ {e-1-j}x ^ n \pmod{x ^ {n+1}} \end{aligned} $$

が成り立ちます．したがって $a=0, b=tp^{e-1-j}$ とすれば，【補題 2】の $H(x)$ について

$$ [x ^ n]H(x) = tp ^ {e-1-j} \cdot p ^ j = tp ^ {e-1}\neq 0 $$

となります．したがって $\deg H(x)\geq n$ となります．一方，【補題 2】より $\deg H(x)\leq L+M-1$ となるため， $n\leq L+M-1$ つまり $L\geq n+1-M$ が従います．$\blacksquare$

4.7. 最小性の証明

更新後の $(L_j,Q_j(x))$ について，$L_j$ の最小性を証明します．

4.7.1. $L _ j$ が増加しない場合

$L_j ^ {\mathrm{new}}=L_j$ が成り立つとします．先頭 $n+1$ 項を処理した時点での補助問題の条件を満たす任意の組は，先頭 $n$ 項を処理した時点での補助問題の条件も満たします．したがって，もし $L_j$ より小さい解が存在したならば，先頭 $n$ 項を処理した時点での $L_j$ の最小性に反します．

よってこの場合，$L_j$ は最小のままです．

4.7.2. $L _ j$ が増加する場合

この場合，$\Delta_j\ne 0$ です．

$$ \Delta_j = t_j p ^ {u_j},\qquad k = e - 1 - u_j $$

とします．まず

$$ L _ j < L_j^{\mathrm{new}} = n + 1 - L_k $$

が成り立つことを示します．参照する補助データが存在しない場合には $L_k = 0$ であり，$L_j^{\mathrm{new}} = n + 1$ なので正しいです．参照する補助データが存在する場合には

$$ L _ j < L_j^{\mathrm{new}} = L _ {B,k} + n - n _ {B,k} $$

が成り立ちます．不変条件より $L _ k = n _ {B,k} + 1 - L _ {B,k}$ なので，

$$ L _ j < L_j^{\mathrm{new}} = n + 1 - L_k $$

となります．

次に，

$$ j+u_k=e-1 $$

を示します．ここで $u_k$ は $\Delta_k = [x ^ n]Q_k(x)S(x)=t_k p ^ {u_k}$ により定まる値です．【補題 2】を

$$ A(x)=Q_j(x),\qquad B(x)=Q_k(x),\qquad L=L_j,\qquad M=L_k $$

として適用します．すると先頭 $n$ 項を処理した時点での係数条件より，

$$ P_j(x):=Q_j(x)S(x)\bmod x^{L_j},\qquad P_k(x):=Q_k(x)S(x)\bmod x^{L_k} $$

は

$$ \begin{aligned} Q_j(x)S(x)-P_j(x) &\equiv \Delta_j x ^ n \pmod{x ^ {n+1}}, \\ Q_k(x)S(x)-P_k(x) &\equiv \Delta_k x ^ n \pmod{x ^ {n+1}} \end{aligned} $$

を満たします．したがって【補題 2】の $H(x)$ について

$$ \begin{aligned} &\deg H(x)\leq L_j+L_k-1, \\ &[x ^ n]H(x)= \Delta_k\cdot [x ^ 0]Q_j(x)-\Delta_j\cdot [x ^ 0]Q_k(x) \end{aligned} $$

が成り立ちます．$\deg H(x) \leq L_j + L_k - 1 \leq n-1$ より $[x ^ n]H(x)=0$ です．一方 $[x ^ 0]Q_j(x)=p ^ j$，$[x ^ 0]Q_k(x)=p ^ k$ なので，

$$ 0 = [x ^ n]H(x)= \Delta_k\cdot p ^ j-\Delta_j\cdot p ^ k = p ^ jt_kp ^ {u_k}-p ^ kt_jp ^ {u_j} $$

が成り立ちます．したがって

$$ t_kp ^ {j + u_k} = t_jp ^ {k + u_j} $$

が成り立ちます．$k = e - 1 - u_j$ であることと，$t _ k, t_ j$ が乗法逆元を持つことより

$$j + u _ k = e - 1$$

が示されました．

これで【補題 3】を適用できます．実際，$R(x)=Q_k(x)$，$M=L_k$ とおくと，先頭 $n$ 項を処理した時点での不変条件より

$$ \begin{aligned} &\deg Q_k(x)\leq L_k, \\ &[x ^ i]Q_k(x)S(x)=0\qquad (L _ k\leq i < n) \end{aligned} $$

が成り立っています．また，上で示した $j+u_k=e-1$ より，

$$ [x ^ n]Q_k(x)S(x)=t_kp ^ {u_k}=t_kp ^ {e-1-j} $$

です．したがって，補題【補題 3】より，先頭 $n+1$ 項についての条件

$$ \begin{aligned} &[x ^ 0]Q(x)=p ^ j,\qquad \deg Q(x)\leq L, \\ &[x ^ i]Q(x)S(x)=0\qquad (L\leq i < n + 1) \end{aligned} $$

を満たす任意の組 $(L,Q(x))$ について $L\geq n+1-L_k$ が成り立ちます．$L_j$ が増加する場合の更新式は

$$ L_j^{\mathrm{new}}=n+1-L_k $$

なので，$L_j^{\mathrm{new}}$ は，先頭 $n+1$ 項を処理した時点での補助問題において最小です．

以上で，すべての場合について $L_j^{\mathrm{new}}$ の最小性が示されました．

4.8. 保存された補助データに関する不変条件の確認

最後に，保存された補助データに関する不変条件が保たれることを確認します．

補助データが更新されるのは，$L _ j$ が増加する場合のみです．この場合の更新式は

$$ B _ j(x):=Q _ k(x),\qquad L _ {B,j}:=L _ k,\qquad n _ {B,j}:=n,\qquad t _ {B,j}:=t_k $$

でした．ここで保存される $Q_k(x),L_k,t_k$ は，先頭 $n$ 項を処理した時点での値です．

まず，先頭 $n$ 項を処理した時点での不変条件より，$\deg Q_k(x)\leq L_k$ です．したがって

$$ \deg B_j(x)\leq L_{B,j} $$

が成り立ちます．また，$Q_k(x),L_k$ は先頭 $n$ 項を処理した時点での補助問題の条件を満たしているので，

$$ [x ^ i]B _ j(x)S(x)=0\qquad (L _ {B,j}\leq i < n _ {B,j}) $$

が成り立ちます．さらに，4.7.2 節で示した $j+u_k=e-1$ を用いると，

$$ [x ^ {n_{B,j}}]B_j(x)S(x) = [x ^ n]Q_k(x)S(x) = t_kp ^ {u_k} = t _ {B,j}p ^ {e-1-j} $$

が成り立ちます．また，4.7.2 節の議論により $\Delta_k\ne0$ であることも分かっているので，$t_k$ は乗法逆元を持ちます．したがって $t_{B,j}=t_k$ も乗法逆元を持ちます．

最後に $L_j^{\mathrm{new}}=n+1-L_k$ より

$$ L_j ^ {\mathrm{new}} = n+1-L_k = n _ {B,j} + 1 - L _ {B,j} $$

が成り立ちます．

以上により，保存された補助データに関する不変条件も保たれることが分かりました．

4.9. 結論，計算量

帰納法により，4.4 節の不変条件はすべての $n$ について成り立ちます．

特に，先頭 $N$ 項をすべて処理した後に $j=0$ を見ると，$[x ^ 0]Q_0(x)=1$ であり，$L_0$ は元の復元問題の最小値です．したがって，疑似コードが返す $(L_0, Q_0(x))$ は，$p ^ e$ を法とする復元問題の解を与えます．

アルゴリズムの計算量は以下の通りです．

正整数 $m$ の素因数分解

$$ m=\prod_{0\leq j < k}p_j^{e_j} $$

が事前に与えられているとします．$E = \sum _ {0\leq j < k} e _ j$ とすれば，Reeds–Sloane アルゴリズムにより，$m$ を法とする復元問題を

$$ \mathrm{O}(N ^ 2E + NE \log m) $$

時間で解くことができます．

4.10. 実装例

SPOJ "FINDLR - Find Linear Recurrence" での AC 実装です．

https://gist.github.com/maspypy/884715fa5e5674f5861c783d4896b962

5. 関連問題

1 は，本講座の復元問題がおおよそそのまま出題されている問題です．

2, 3 は合成数を法として線形漸化的数列の第 $K$ 項を求めるタイプの問題です．

6. まとめ

本講座では，

線形漸化的数列

で扱った復元問題を発展させ，一般の $m$ について，$\mathbb{Z}/m\mathbb{Z}$ 上での線形漸化式の復元問題を扱いました．なお，

線形漸化的数列の第 K 項

のアルゴリズムは一般の単位的可換環上で扱えるので，Berlekamp–Massey アルゴリズムと Bostan–Mori アルゴリズムを組み合わせる方法と同様のことが $\mathbb{Z}/m\mathbb{Z}$ においても行えることになります．

7. 参考文献

James A. Reeds, N. J. A. Sloane．Shift-Register Synthesis (Modulo m)．SIAM Journal on Computing．Vol. 14．No. 3．pp. 505–513．1985．DOI: 10.1137/0214038．https://doi.org/10.1137/0214038．

トップページ：AtCoder Algorithm Lectures

質問・誤植報告・補足情報など：Discord サーバー