FPS基本演算と多項式の多点評価を行う

概要

形式的べき級数の基本演算

定数項条件と次数打切りを確認し、Newton iterationでinverse・log・exp等を畳み込みへ還元する。

考え方

FPSでは収束を考えず、mod x^N、つまり0,…,N−1次の係数だけを求める。積の低次係数は入力の低次係数だけで決まるので、各段で必要精度に打ち切ってよい。以下では係数を体上で扱い、積分で割る1,…,N−1が可逆であるとする。

逆元: 誤差を二乗して精度を倍にする

Aの定数項A_0≠0なら、AB=1を満たす逆元は係数ごとに一意に決まる。B_0=A_0^(-1)、n≥1ではB_n=−A_0^(-1)Σ_{i=1}^n A_i B_{n-i}となるが、直接計算はO(N²)。

AB≡1 mod x^mまで求まったBを、B_new=B(2−AB) mod x^(2m)で更新する。E=1−ABはx^mの倍数なので、1−AB_new=(1−AB)²=E²≡0 mod x^(2m)。これが倍増の不変量である。B=A_0^(-1)、m=1から始め、Aを2m項まで読み、二回の畳み込みと加減算でB_newを求める。最後の精度はmin(2m,N)でよい。

対数: 微分・逆元・積分へ分解する

A_0=1のときlog Aを、定数項0かつ(log A)'=A'/Aを満たす級数として定義する。A'=Σ_{i≥1}iA_i x^(i−1)、積分は∫C=Σ_{i≥0}C_i x^(i+1)/(i+1)とし、積分定数は0とする。

log A mod x^Nを求める手順は、A'をN−1項まで作り、逆元A^(-1)との積をmod x^(N−1)で計算し、積分してN項へ戻すことである。微分で精度が一つ下がるので、積をN−1項まで求めれば足りる。A_0≠1では体上のlog A_0を別に定義する必要があり、この基本演算では扱わない。

指数: 対数の誤差を掛けて補正する

F_0=0のときexp Fは、B_0=1かつB'=F'Bを満たす級数である。係数ではnB_n=Σ_{i=1}^n iF_i B_{n-i}となり、上の可逆性条件の下で一意に定まる。これはlog B=Fを解くことと同じなので、B=1、m=1から始める。

log B≡F mod x^mを保ち、H=F−log B mod x^(2m)、B_new=B(1+H) mod x^(2m)で更新する。Hはx^mの倍数なので、log(1+H)≡H mod x^(2m)。従ってlog B_new≡log B+H≡F mod x^(2m)となる。これは方程式log B−F=0のNewton補正で、微分が1/Bとなるため補正にBを掛ける。

各段では既知のBを高次0で延長して、その延長のlogを目標精度まで求めてから補正する。未知係数を既知の正解として扱うのではなく、誤差がx^mから始まることを利用する。例えばF=xなら、最初の更新はB=1+x、次はB=1+x+x²/2+x³/6 mod x^4となる。

冪: 指数をループ回数から係数へ移す

A_0=1で非負整数K乗をN項まで求めるとき、B=A^KはB_0=1、A B'=K A' Bを満たす。x^(j−1)の係数を比較してj b_j=Σ_{i=1}^j((K+1)i−j)a_i b_{j−i}となる。j=1,…,N−1の昇順に割ればO(N²)時間・O(N)空間で、Kの大きさに比例する処理やlog K回の積は不要である。小次数の冪を集合ごとに求めるABC294 Exに向く。

次数が大きい場合はB=exp(K log A)を使い、上記の逆元・log・expを通してO(M(N))で求められる。どちらも1,…,N−1が可逆という仮定を使う。標数pでN>pとなる場合、微分からp次係数は一意に決まらないので、そのまま同じ再帰を使わない。

定数項がc≠0ならA/cへ正規化して、その冪にc^Kを掛ける。定数項0の非零級数ならA=x^v c U、v>0,U_0=1と分解し、A^K=x^(vK)c^K U^K。vK≥Nなら全N項が0、それ以外はUをN−vK項まで計算してshiftする。K=0はAにかかわらず単位元1、零級数の正の冪は0とする。二分累乗と異なる計算量を主張する際は、どの定数項条件の下でどの冪手順を使うかまで決める。

成立条件と計算量

目標精度Nで積分・expを扱うには、標数0の体、または素数標数pでN≤pとすれば1,…,N−1を割れる。逆元だけなら必要なのはA_0の可逆性で、積分の標数条件は不要。畳み込みをNTTで行う場合は、この標数条件に加えて法と変換長の条件も満たす必要がある。

乗算費用をM(n)とする。逆元とexpの倍増各段は定数回の乗算と、expではその段のlog・逆元計算を含めてO(M(m))である。M(n)=O(n log n)なら、M(1)+M(2)+…+M(2^k)=O(2^k k)=O(M(N))となる。logも一回の逆元と乗算でO(M(N))。この和の評価により、倍増の段数だけ機械的にlog Nを掛ける必要はない。単純な畳み込みを使えば同じ式でもO(N²)となる。

下位単元

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 橙色(2400–2799)。定数項と打切り次数の条件を押さえ、Newton反復で逆数・log・expを構成する。

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

概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-formal-power-series

習得する技能

  • 定数項の前提と次数打切りを確認し、Newton法を用いたFPSの逆数・対数・指数などを畳み込み計算へ還元できる。

前提と範囲

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

直接の前提単元: 組合せを生成関数へ符号化する、NTT・FFTで畳み込みと相互相関を求める。

このUnitを直接前提とする単元: FPS合成・power projection、多項式の多点評価・補間。

生成関数の係数解釈と高速畳み込みを再利用し、Newton法による逆数・log・expを次数制限付きで実装し、多点評価と補間へ進む。有理母関数の係数抽出と一般FPS合成は独立した節で学ぶ。

このUnitでは扱わないもの

  • 積を一回求めるだけの畳み込み、および生成関数へ符号化するだけで高度な多項式演算を使わない計数。

根拠