Bostan–Mori・有理生成関数の係数抽出
概要
P(x)/Q(x)のN次係数をQ(-x)との積の偶奇係数へ半減し、対数段で巨大indexへ進む。
考え方
有理級数P(x)/Q(x)の第K係数を求める。Q(−x)を掛けると分母が偶数次数だけになり、分子のKの偶奇に合う係数だけを残してKを半分へ縮められる。
具体的にはU(x)=P(x)Q(−x)、V(x)=Q(x)Q(−x)を畳み込みで作る。V(−x)=V(x)で奇数係数が消える。標数2でもQ(−x)=Q(x)の平方の奇数係数は0である。ε=K mod 2として P'_i=U_(2i+ε)、Q'_i=V_(2i)、K'=(K−ε)/2へ置換する。分母が偶数冪だけなので [x^K]P/Q=[y^K']P'(y)/Q'(y) となり、目標係数を保存する。Q'(0)=Q(0)²は可逆性を保つ。
Kが0になるまでこの更新を繰り返し、最後にP(0)/Q(0)を返す。deg P<deg Q=dなら各更新でもdeg P'<d、deg Q'≤dで、O(log(K+1))段の多項式積に収まる。初めの分子が高次数ならP=HQ+Rへ分け、Hの第K係数を先に足してR/Qに適用する。
成立条件と計算量
分母次数dならO(M(d) log K)。Q(0)が可逆であることが必要。分子が分母以上の次数なら商の寄与を分ける。偶数・奇数係数の抽出添字とK=0の停止値を確認する。
問題一覧
- ABC300 Ex「Fibonacci: Revisited」 公式問題
技能・出典
主題: Bostan–Mori・有理生成関数の係数抽出(P(x)/Q(x)のN次係数をQ(-x)との積の偶奇係数へ半減し、対数段で巨大indexへ進む。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 固定線形遷移を巨大回数進める(固定線形遷移を行列または漸化式にし、巨大回数後の値を求められる。) / NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。主タグ: Bostan–Mori・有理生成関数の係数抽出 / 補助タグ: 畳み込み・相互相関、線形遷移・行列累乗
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 橙色(2400–2799)。有理母関数の係数を偶奇で分け、指数を半減する変形を繰り返す。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-bostan-mori
Bostan–Mori・有理生成関数の係数抽出
習得する技能
- P(x)/Q(x)のN次係数をQ(-x)との積の偶奇係数へ半減し、対数段で巨大indexへ進む。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 組合せを生成関数へ符号化する。
このUnitを直接前提とする単元: なし。
生成関数による組合せ構造の符号化で得た考え方と実装を再利用し、Bostan–Mori・有理生成関数の係数抽出の発動条件・正当化・境界を重複なく学ぶ。
このUnitでは扱わないもの
- Bostan–Mori・有理生成関数の係数抽出の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。