読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 215 メモ 高速きたまさ法

yukicoder 実装メモ

間違ってるかもしれないけど解法の方針が分かった気がした。
実装している時間がないのでとりあえずメモ

まずM項間漸化式をO(M^2)で作成する。
これはEASY,MEDを解いてる人ならできてると思うので省略。


きたまさ法の説明は省略。
剰余環での畳み込み和をフーリエ変換してO(M\log M)でできることを前提とする。
(ちなみに高速フーリエ変換の仕組みすら理解していない)

係数の畳み込みをO(M^2)でとってできた要素2M個の数列を要素M個の数列にO(M^2)で変換して
それを O(\log N)回繰り返して結果O(M^2 \log N)でM項間定数係数漸化式のN項目を求めるのが従来のきたまさ法。

このO(M^2)の部分をO(M \log M)にしたのが高速きたまさ法。

まずP= \{p_1,p_2,,,,p_M \}Q= \{q_1,q_2,,,,q_M \}の畳み込み和をとってA'=P*Q= \{a'_1,a'_2,,,a'_{2M} \}と畳み込み演算を行う。
ここだけに関してはFMTをかけるだけなのでO(M \log M)



ここからが大問題


A'= \{a'_1,a'_2,,,a'_{2M} \}

A = \{a_1,a_2,,,a_M \}に直したい

この補正に使う式はM項間定数係数漸化式a_{k+M+1}=\sum_{i=1}^M c_{M-i} a_i
(cの係数の順番はこの逆のパターンもありますがライブラリの関係上こう書かせてください。)


愚直に計算してAを求めるとO(M^2)
でもよく考えると最終的にa_k =a'_k+\sum_{i=1}^M b_{ki}a'_{M+i}(1 \le k \le M) となる定数列B_k=\{b_{k1},b_{k2},,,b_{kM} \}があるはず。
ちなみにkごとに定数列が異なるってことに気づかずに3時間ぐらい間違った解法で実装していた()

こんな感じの式ならうまく分解すれば畳み込み和の形に変換できそうっていうのが最初のアプローチ。
畳み込み和の形にできたらフーリエ変換して勝ち。だから頑張って変形する。




ここから超試行錯誤した結果なのでぐちゃぐちゃ。
S'= \{s'_1,s'_2,,,s'_{2M} \}=\{ 0,0,,,,s \}a_{k+M+1}=\sum_{i=1}^M c_{M-i} a_iを適用させてM個の要素に変形した数列Sを求める。
t_0 = 1
t_k = \sum_{i=0}^{k-1}t_{i} C_{M-(k-i)}(x<0のときC_{x}=0)
とすると
S=\{t_{2M-1}s,t_{2M-2}s,,,t_1s,t_0s\}という風になります。これはただのパズル。

なんだ!T=\{t_1,,,t_{2M-1}\}が分かればa_k=a'_k+\sum_{i=M+1}^{2M}t_{i-k}a_iになるからちょっと変形して畳み込みでAが求まるじゃんと思った私を含むあなた。実はこれ間違いです。
でもここに書いたってことはこのtの値を使えば求まる(はずだ)からです。

何が問題かっていうと
a_M=a'_M+t_1a_{M+1}+,,,+t_Ma_{M+M}は正しいけど
a_1=a'_1+t_1a_{1+1}+,,,+t_Ma_{1+M}は正しくないです。
a_Mにおけるa'_{M+M}の係数t_Mは正しいけれどa_1におけるa'_{1+M}の係数t_Mは正しくないんです。
双方のt_Mを比較すると
前者は\sum_{i=0}^{M-1}t_{i} C_{i}で正しいですが
後者は間違いで、正しい係数はt_0C_{0}です。


a_k (1 \le k \le M)について考えます。
a_k = \sum_{i=M+1}^{2M} f(k,i)a'_iとします。係数fはk,iの2変数に依存します。これは正しいはず。
f(k,i)について,k=Mのときt_{i-k}が成り立ちます。
これは問題ないです。
 k < Mのとき\sum_{j=0}^{i-(M+1)}t_{j}C_{M-((i-k)-j)}となります。
k=Mのときもこの式が成り立つので結果的にf(k,i)=\sum_{j=0}^{i-(M+1)}t_{j}C_{M-((i-k)-j)}が正義
a_k=\sum_{i=M+1}^{2*M}\sum_{j=0}^{i-(M+1)}t_{j}C_{M-((i-k)-j)}a'_i
=\sum_{i=M+1}^{2M}(t_{i-k}-\sum_{j=i-M}^{i-k-1}t_jC_{M-((i-k)-j)})a'_i
この変形をすると,f(i,k)はi-kという値のみに依存する係数だということが分かります。
あらかじめi-kについて係数を求めておきそれをg(i-k)とおくと
a_k=\sum_{i=M+1}^{2*M} g(i-k) a'_i



打ち消し線の方針で解けなかったので考え直したらなんとかなりそうになりました。
t_1,,,t_Mによる遷移はa'_M,,,a'_{2M}内でのみ有効です。
この範囲であればa"_k=\sum_{i=k}^{2M}t_{i-k}C_iが正しくなります。
畳み込み演算により求められたa"_{M+1},,,a"_{2M}からC_kを使って遷移してやればよいです。
ここも畳み込み演算で求められ、正しい解が求められるはず。

ACしたらライブラリ整備して書き直します。