概要
「分割統治FFT」というと特に https://atcoder.jp/contests/abc213/editorial/2396 みたいなタイプを指すような会話を少し見たことがあるのですが，どのくらい一般的な用語なのか分からず．
私は雑に，分割統治と FFT を組み合わせて答が求められる系のテクニックをすべて分割統治＋FFTと見なしているのですが，用語が分かりにくいなどあればご指摘ください．
問題によって微妙に求められる考察や実装が変わる印象もありますが，共通のテンプレパターンと見なせると考察や実装の楽ができて便利だと思います．
ここでは，複数の問題に適用できそうなパターンを 2 つ紹介します．
パターン 1
$L_i, R_i, f_i$ を低次の Laurent 多項式とするとき，
$$\sum_{i} \Bigl(\prod_{0\leq k < i}L_k\Bigr) f_i \Bigl(\prod_{k < i < N}R_k\Bigr)$$
を求める問題．区間に対して答・$L$ の総積・$R$ の総積という 3 つ組を求めることを考えて分割統治で再帰的に計算すれば $O(N\log^2N)$ 時間で解ける．
一般化として，これらは行列でも構わない．$L_i$ は $(a,a)$ 行列，$f_i$ は $(a,b)$ 行列，$R_i$ は $(b,b)$ 行列といった型になる．
多項式の総積
$R_i$ がすべて $1$，$f_i$ が最後だけ $1$ の場合にあたる．
有理式の総和
$\dfrac{X}{Y}+\dfrac{a}{b} = \dfrac{bX+aY}{bY}$ より，有理式 $\dfrac{a}{b}$ を足すことを線形変換 $\begin{pmatrix}X\\Y\end{pmatrix} \longmapsto \begin{pmatrix}bX+aY\\bY\end{pmatrix}$ と見なせば，有理式の総和の分子・分母の計算は $\begin{pmatrix} b & a \\ 0 & b\end{pmatrix}$ の形の行列の総積の計算と考えられる．よってこれは上のパターンの例として扱える．
その他の問題例
- ■ パスグラフの場合には $\sum_i \prod_{0\leq k<i}f_k$ の形の計算になる．
- ■ $\sum_{L} c_Lx^{N-L} \prod_{i=0}^{L-1}(M-x-i)$ という式が登場．$L_i(x) = M-x-i, R_i(x) = x$ とする．
パターン 2
形式的 Laurent 級数 $f(x)$ と低次の Laurent 多項式 $L_i, R_i$ が与えられるので，各 $i$ に対して
$$[x^0] \Bigl(\prod_{0\leq k < i}L_k\Bigr) f(x) \Bigl(\prod_{k < i < N}R_k\Bigr)$$
を求める問題．分割統治で現れる区間に対する $L$ や $R$ の総積を事前に計算しておけば分割統治できる．答の計算では長さ $n$ の区間で興味のある $f$ の項が $O(n)$ 項しかない（とても低次・高次の項は捨ててよい）ことから計算量が $O(N\log^2N)$ 時間におさえられる．
多点評価
$f(x)$ を多項式とするとき，$f(a) = [x^0]f(x^{-1})\cdot (1-ax)^{-1}$ である（参考：https://codeforces.com/blog/entry/100279）．
$F(x) = f(x^{-1})\prod_{a}(1-ax)^{-1}$ とすれば，$f(a_i) = [x^0] F(x)\prod_{k\neq i}(1-a_kx)$ である．よってパターンにおいて $L_i = R_i = 1-a_ix$ とした場合に相当する．
prefix product に対する多点評価
- https://judge.yosupo.jp/problem/many_factorials （解説：https://suisen-kyopro.hatenablog.com/entry/2023/11/22/201600）
$x(x+1)\cdots (x+k-1)$ を $x=n$ で評価せよというタイプのクエリをたくさん計算したい．
多点評価を少し改造して，評価する点の prefix において適切な 1 次式を余分に掛け算されるようにすればよい．
- ■ こちらは $(2,2)$ 行列の prefix product に関する多点評価．
その他の問題
- ■ いろんな $i$ に対して $[x^0] F(x)f(x)^i$ を求める問題に帰着できる．
- ■ prefix product の係数を求める問題ですが，$L_i$ が $i$ に対する答を使って動的に定まるという問題になっています．
- ■ この方法を使う計算量改善をユーザー解説として書きました．
- ■ 難しい．$L_i$ を $(2,2)$ 行列，$R_i$ を $(1,1)$ 行列としてパターンに当てはめることができる．
注意
一般の行列で抽象化する場合，パターン 2 の積の順序がこのままではまずそう．
