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

1. 概要 転置原理は，ある問題の解法から別の問題（転置問題）の解法を機械的に導出するという，意外性のある面白い考え方です． 特に多項式の多点評価のアルゴリズムの定数倍高速化が転置原理を通して発見されたことが有名です．他には形式的べき級数の合成…