多項式の多点評価・補間

概要

一般点ではproduct tree・remainder tree、等比点ではchirp-z変換を使い、評価点の構造に応じて多項式を一括評価する。

一般点:積木と剰余木

任意の点x_iについて葉をX−x_iとするproduct treeを作り、親の剰余を子の積で割った剰余へ送る。葉の定数がf(x_i)になる。次数nと点数mが同程度ならO(M(n) log n)、NTTを用いてO(n log² n)。評価点の規則性を仮定しない。ABC272 Exでは計数DPを評価値へ変換する前段の式も別に導く。

等比点:chirp-z変換

x_k=a r^kならf(x_k)=Σ_j c_j a^j r^{jk}。jk=C(j+k,2)−C(j,2)−C(k,2)を使い、c_j a^j r^{−C(j,2)}とr^{C(t,2)}の相関へ直す。係数列を反転して一回の畳み込みを行い、r^{−C(k,2)}を掛ければよい。r≠0なら平方根を導入せず任意の体で成立する。r=0は点aと0の直接評価へ分ける。計算量O(M(n+m))で、一般多点評価のlog因子を不要にする。

ABC381 Gでは、拡大体で数列を表す→等比的な因子積を倍化構築する→block始点で等比点評価する、という接続までを学ぶ。評価算法を知るだけで積の高速計算が終わるわけではない。拡大体の積は基礎体の複数の畳み込みへ分解する。

考え方

評価点x_iに対応するX−x_iの積木を作り、fを各部分木の積で割った剰余を下へ送る。葉では定数剰余がf(x_i)になる。

剰余の計算と補間の復元

親でR≡f mod P_parentを保ち、子の積P_childはP_parentを割るため、R mod P_child=f mod P_child。これがremainder treeの不変量で、葉X−x_iでの定数剰余がf(x_i)となる。高速な多項式除法には、次数dのRと次数eのmonic Pを逆順にした多項式を使う。d≥eなら商Qの逆順は rev_d(R)·rev_e(P)^(−1) mod X^(d−e+1)。rev_e(P)の定数項は1なのでFPS逆元を作れ、商を逆順に戻してR−QPから剰余を得る。d<eならRがそのまま剰余である。

異なる点の値y_iから補間する場合、全点の積P(X)=∏(X−x_i)とP'を作り、上の多点評価でP'(x_i)を得る。w_i=y_i/P'(x_i)とし、葉の補間要約をw_i、左右の積をP_L,P_R、要約をF_L,F_Rとして F_parent=F_L P_R+F_R P_L で併合する。根ではΣ_i w_i P(X)/(X−x_i)となり、x_jで代入するとj項だけが残ってy_jへ戻る。重複点ではP'(x_i)=0となり、この補間式は使えない。

成立条件と計算量

次数と点数がN程度ならO(M(N) log N)。等比点にはchirp-zによるO(M(N))の方法があるが、比率が非零である条件を確認する。評価点重複は評価できても補間の一意性とは別である。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 橙色(2400–2799)。一般点の積木・剰余木と等比点のchirp-zを比較し、評価点の構造から変形と計算量を選ぶ。

対象色の読み方は本書の読み方を参照してください。

概念上の親: FPS基本演算と多項式の多点評価を行う。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-polynomial-multipoint-evaluation

多項式の多点評価・補間

習得する技能

  • 評価点ar^kの等比構造を使い、r≠0のとき二項指数の恒等式からchirp-z評価を一回の畳み込みへ変形できる。
  • 任意の評価点からproduct treeを構築し、剰余をremainder treeで下ろす不変量とO(M(n) log n)の計算量を説明できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: FPS基本演算と多項式の多点評価を行う、再帰分割・分割統治。

このUnitを直接前提とする単元: なし。

形式的べき級数の基本演算・再帰分割・分割統治で得た考え方と実装を再利用し、多項式の多点評価・補間の発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • 多項式の多点評価・補間の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠