1. 概要 本講座では，正整数 $\boldsymbol{m}$ を法とする線形漸化式の復元問題を扱います． 線形漸化式の復元 では，数列から定数係数線形漸化式を復元する問題を，係数環が体である場合に解説しました．その場合のアルゴリズムの代表が Berlekamp–Massey …

1. 概要 本講座では，数列から定数係数線形漸化式を復元する問題について解説します． 例えば，Fibonacci 数列の先頭項 $$ S=(0,1,1,2,3,5,8,13) $$ を入力として，この数列が満たす漸化式 $$ S _ i = S _ {i-1} + S _ {i-2} $$ を出力するような問題を考え…

1. 概要 本講座では，Bostan–Mori のアルゴリズムに関する発展的な話題を扱います． 前回の講座 線形漸化的数列の第 K 項 では，線形漸化的数列の第 $K$ 項を高速に求める方法として，Fiduccia のアルゴリズムと Bostan–Mori のアルゴリズムを解説しました．…

1. 概要 単位的可換環 $R$ 上の数列 $A = (A_0,A_1,A_2,\ldots)$ が，定数 $c_1, c_2, \ldots, c_d$ について $$ A _ i = c_1 A _ {i-1} + c _ 2A _ {i-2} + \cdots + c _ dA _ {i-d}\qquad(i\geq d) $$ を満たすとします．このような数列を線形漸化的数列と…

解説動画はこちらです． 1. 概要 本講座では，線形漸化的数列について解説します． 線形漸化的数列とはある種の漸化式を満たす数列のことで，代表例としては漸化式 $$ F _ i = F _ {i-1} + F _ {i-2}\quad (i\geq 2) $$ を満たす Fibonacci 数列 $$ F = (0, …

1. 概要 本講座では，競技プログラミング（あるいは AtCoder Algorithm Lectures）での使用頻度が高い，代数構造に関する用語および，その代表例について解説します． 代数構造は典型的には，集合と集合上の演算の組として定義されます．例えば，整数に対す…

1. 概要 本講座では，ある種の dp を高速化するテクニックについて解説します． 線形代数を学んだことがある方は，固有値・固有ベクトルあるいは行列の対角化によって行列の $M$ 乗計算を高速化する手法を見たことがあるかもしれません．本講座の内容は，同…

1. 概要 正整数の $0$ 乗和， $1$ 乗和， $2$ 乗和， $3$ 乗和について $$ \begin{aligned} \sum _ {n = 1} ^ N n ^ 0 &= N,\\ \sum _ {n = 1} ^ N n ^ 1 &= \frac12 N(N+1) = \frac12 N ^ 2 + \frac12 N,\\ \sum _ {n = 1} ^ N n ^ 2 &= \frac16 N(N+1)(2N+…

1. 概要 本講座では，$\mathbb{F}_p$ 係数の多項式に関する重要事項について解説します． 議論の大部分は，多項式について中学・高校の数学で学んだ内容の再確認になると思います．ただし，中学・高校の数学では，多項式の係数として主に実数（や複素数）を…