母関数方程式・高度な係数抽出
概要
暗黙方程式の反転、微分恒等式の係数比較、Euler積の疎な展開を使い分け、必要次数の係数を求める。
母関数を立てた後、式の形から係数抽出法を選ぶ。F=xΦ(F)にはLagrange反転 [x^n]F=(1/n)[t^(n−1)]Φ(t)^nを使う。Fの定数項は0、Φの定数項は可逆として一意な形式的解を扱い、法上ではnで割れる範囲を確認する。
ABC222 Hでは反転後にP(x)^m、P=1+3x+x²、m=2Nの係数u_kを求める。P U′=m P′ Uの係数比較から k u_k=3(m+1−k)u_(k−1)+(2m+2−k)u_(k−2)。u_0=1、負添字は0とし、答えはu_(N−1)/N。反転で求める係数を変える工程と、微分で係数漸化式を得る工程を分ける。
ABC230 Hでは対数微分から係数再帰を得た後、その畳み込みをオンラインに計算する。係数漸化式の導出と、既に得た漸化式の高速評価は別の技能である。
ABC279 ExではEulerの五角数定理 ∏_{i≥1}(1−x^i)=1+Σ_{t≥1}(−1)^t(x^{t(3t−1)/2}+x^{t(3t+1)/2})を使う。必要次数d以下にはO(√d)項しかない。有限積を延長するときは追加因子の最小次数がdを超えることを確認する。各項に掛ける巨大引数の二項係数は、組合せ係数の節のLucasの定理へ接続する。
考え方
生成関数の等式を得た後、微分で係数漸化式を作る、Euler積を疎に展開する、Lagrange反転で合成方程式を解くなど、式の形に合う係数抽出を選ぶ。
Lagrange反転の係数変換を導く
まず標数0でF=xΦ(F)、Φ(0)≠0を扱う。形式級数の留数ResはX^(−1)の係数と定義する。g(t)=t u(t)、u(0)≠0の変数変換では Res_x H(x)=Res_t H(g(t))g'(t)。これはH=x^jで確認できる。j≠−1では右辺が(g^(j+1))'/(j+1)となり微分の留数は0、j=−1ではg'/g=1/t+u'/uで留数1である。
Fの逆変換はx=t/Φ(t)。従ってn≥1で [x^n]F=Res_x F/x^(n+1) を置換すると Res_t (t^(−n)Φ(t)^n−t^(1−n)Φ(t)^(n−1)Φ'(t))。第一項は[t^(n−1)]Φ^n、第二項は[t^(n−2)](Φ^n)'/n、すなわち(n−1)/n倍の同係数なので、差は [t^(n−1)]Φ^n/n になる。これで合成方程式の未知係数を既知の多項式冪へ移せる。有限体ではnを掛けた係数恒等式へ戻して適用し、nの逆元がある範囲でのみこの除算式を使う。
成立条件と計算量
係数を一つ求めるかN個求めるかで適した算法が変わる。分母の可逆性、形式級数の定数項、反転公式の次数条件を確認する。式を得ただけでは高速な係数抽出の計算量は確定しない。
問題一覧
- ABC279 Ex「Sum of Prod of Min」 公式問題組合せ: 組合せ係数と対称性で数える
技能・出典
主題: 母関数方程式・高度な係数抽出(Eulerの五角数定理により∏(1−x^i)を符号付きの疎な係数列へ展開し、必要次数までのO(√N)項で係数抽出できる。)。既習技能: 組合せ係数と対称性で数える(素数pのもとでn,kをp進展開し、Lucasの定理 C(n,k)=∏C(n_i,k_i) mod pで、n≥pでも階乗の零除算を避けて計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 母関数方程式・高度な係数抽出 / 補助タグ: 組合せ係数・数え上げ
- ABC222 H「Beautiful Binary Tree」 公式問題組合せ: 法上の四則演算・高速累乗・逆元
技能・出典
主題: 母関数方程式・高度な係数抽出(F=xΦ(F)からLagrange反転 [x^n]F=[t^(n−1)]Φ(t)^n/nを導き、形式的条件と法上の除算可能性を確認して係数問題へ変換できる。)。追加で学ぶ技能: 母関数方程式・高度な係数抽出(母関数の微分恒等式を作り、次数ごとの係数比較から初期値・分母条件を持つ漸化式を導ける。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。)。主タグ: 母関数方程式・高度な係数抽出 / 補助タグ: 法上の四則演算・高速累乗・逆元
- ABC230 H「Bullion」 公式問題
技能・出典
主題: 母関数方程式・高度な係数抽出(母関数の微分恒等式を作り、次数ごとの係数比較から初期値・分母条件を持つ漸化式を導ける。)。追加で学ぶ技能: Relaxed・online convolution(係数が順に確定する因果的畳み込みをblock分割し、確定済みblock間だけをNTTでまとめて更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。)。主タグ: 母関数方程式・高度な係数抽出、Relaxed・online convolution / 補助タグ: 再帰分割・分割統治
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 橙色(2400–2799)。Lagrange反転・微分による係数比較・Euler積を、式の条件に合わせて選ぶ。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-generating-function-coefficients
母関数方程式・高度な係数抽出
習得する技能
- 母関数の微分恒等式を作り、次数ごとの係数比較から初期値・分母条件を持つ漸化式を導ける。
- Eulerの五角数定理により∏(1−x^i)を符号付きの疎な係数列へ展開し、必要次数までのO(√N)項で係数抽出できる。
- F=xΦ(F)からLagrange反転 [x^n]F=[t^(n−1)]Φ(t)^n/nを導き、形式的条件と法上の除算可能性を確認して係数問題へ変換できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 組合せを生成関数へ符号化する。
このUnitを直接前提とする単元: なし。
生成関数による組合せ構造の符号化で得た考え方と実装を再利用し、母関数方程式・高度な係数抽出の発動条件・正当化・境界を重複なく学ぶ。
このUnitでは扱わないもの
- 母関数方程式・高度な係数抽出の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。