[yukicoder] No.2166 Paint and Fill

概要
公式解説補足
解法（制約 1）

概要

問題文 → ■
公式解説 → ■
自分の提出 → ■

制約 1 の取り扱いが、少し別解っぽかったので書いておきます。

公式解説補足

$[x^{0}] f = 1$ となる（疎な）多項式と定数 $N$ に対して、 $F_{k} = [x^{k}] f (x)^{N}$ で定まる数列 ${F_{k}}$ は p-recursive になります。

$F = f^{N}$ とすると、対数微分 $\frac{F^{'}}{F} = \frac{N f^{'}}{f}$ から分かる式 $f F^{'} = N f^{'} F$ から $F$ の係数の間の関係式が得られるためです。したがって、本問の解はテストケースごとに $O (K)$ 時間で計算できます。

これをさらに高速化することが求められています。

解法（制約 1）

クエリ総数を $Q$ 、クエリを表す文字は $(n, k)$ として、 $k$ の最大値を $K$ と書きます。

上述の係数間の漸化式を行列で書き表すことで、次に帰着できます：

$0 ≦ j < K$ に対して、 $1$ 次多項式を成分とする $(2, 2)$ 行列 $F_{j} (x)$ が与えられる。
$(n, k)$ に対して次を求めるクエリに $Q$ 回答えよ： $F_{k - 1} (n) \dots F_{0} (n) (\begin{matrix} 1 \\ 0 \end{matrix})$ .

適当なバケットサイズ $B$ を設定して、各 $i$ に対して次を行うことで解きます。

区間積 $\prod_{j \in [B i, B i + B)} F_{j} (x)$ を計算する。ただし積は $j$ について降順。計算結果は $B$ 次多項式を成分とする $(2, 2)$ 行列。
区間積 $\prod_{j \in [0, B i)} F_{j} (x)$ を計算する。（やはり $j$ について降順）
$k \in [B i, B i + B)$ を満たすクエリ $(n, k)$ に対して、2. の区間積を $x = n$ で評価したもの $\prod_{j \in [0, B i)} F_{j} (n)$ を計算する。
$k \in [B i, B i + B)$ を満たすクエリ $(n, k)$ に対して答を計算する。

それぞれの方法と計算量を確認します。

は $1$ 次式 $B$ 個の総積で、分割統治と畳み込みを利用して $O (B \log^{2} B)$ 時間でできることがよく知られていると思います（関連：https://judge.yosupo.jp/problem/product_of_polynomial_sequence）。すべての $i$ にわたる計算量の合計は $O (K \log^{2} B)$ 時間です。
は、1. の結果を順番に畳み込むことで行います。畳み込みが $O (K \log K)$ 時間、これを $O (K / B)$ 回行うため、 $i$ にわたる和は $O (K^{2} \log K / B)$ 時間です。
は、2. の結果を成分ごとに多点評価することで得られます。バケット内のクエリの個数を $Q_{i}$ として、 $O (K \log K + Q_{i} \log^{2} Q_{i})$ 時間。バケットに関する総和は $O (K^{2} \log K / B + Q \log^{2} Q)$ 時間です。なお、以下に述べるように、最終的にはこの行列に $(\begin{matrix} 1 \\ 0 \end{matrix})$ をかけたものだけが必要なので、多点評価を行う成分は $2$ つだけでよいです。
は、3. で計算した $(\prod_{j \in [0, B i)} F_{j} (n)) \cdot (\begin{matrix} 1 \\ 0 \end{matrix})$ に対してさらに $j = B i, \dots, k - 1$ の順に左から行列 $F_{j} (n)$ をかけることで行います。行列行列積ではなく行列ベクトル積を反復する方が定数倍がよいです。バケット内のクエリの個数を $Q_{i}$ として、 $O (Q_{i} B)$ 時間。バケットに関する総和は $O (Q B)$ 時間です。

$X = max (K, Q)$ として、計算量に現れた項を見ていくと、全体の計算量は $O (X^{2} \log X / B + X \log^{2} X + X B)$ と書けることが分かります。 $B = \sqrt{X \log X}$ とすることで、全体の計算量は $O (X^{1.5} \sqrt{\log X})$ となります。実装の定数倍を減らしバケットサイズを調整することで、この方針で AC することができます。

$X^{2} \log X / B$ の定数倍が重く、 $X B$ の定数倍が軽いからか、 $B$ は $\sqrt{X \log X}$ よりもかなり大きくとった方が実行時間が短くなりました。