F - Montage 解説 by maspy

より計算量オーダーのよい解法

時間計算量 \(O(NM\log NM)\) での解法を紹介します．

公式解説を前提とします．「形式的べき級数」を「FPS」と略記します．

各 \((n, m)\) （\(0\leq n\leq N, 0\leq m\leq M\)）に対して次を計算することに帰着されるのでした：

\((0,0)\) から \((n,m)\) に格子上を最短経路で進むパスの 2 つ組であって，パス 1 が常にパス 2 の右上側にあるものを数えよ．（同じ点を通ることは許容するが，同じ辺を通ることは許容しない．）

これは，パスの 2 つ組を同時に 1 マスずつ進めていく dp をすれば，\(\Theta((N+M)^3)\) 時間で計算できます．

この計算をさらに高速化しましょう．

上述の数え上げを \(a_{n,m}\) とします．次の数え上げを \(b_{n,m}\) とします：

\((0,0)\) から \((n,m)\) に格子上を最短経路で進むパスの 2 つ組であって，パス 1 が常にパス 2 の右上側にあり，\((n,m)\) で初めて同じ点を通るものを数え上げよ．

対応する 2 変数 FPS を

\(A(x,y) = \sum_{n,m}a_{n,m}x^ny^m,\qquad B(x,y) = \sum_{n,m}b_{n,m}x^ny^m\)

とすると，次が成り立ちます：\(A(x,y) = \sum_{k=0}^{\infty}B(x,y)^k = (1-B(x,y))^{-1}.\)

\(B(x,y)^k\) の部分が，\((n,m)\) に至るまでにちょうど \(k\) 回ぶつかるようなパスの組の個数に対応します．

\(b_{n,m}\) は最初と最後の 1 歩ずつを除いて考えると

  • \((0,1)\) から \((n-1,m)\) への格子上の最短路 1
  • \((1,0)\) から \((n,m-1)\) への格子上の最短路 2

の組であって，頂点を共有しないものを数えればよいことが分かります．これは例えば LGV 公式で計算できます．二項係数の前計算のもと，ひとつあたり \(O(1)\) 時間です．

2 変数 FPS \(B(x,y)\) が与えられたときに \(A(x,y) = (1-B(x,y))^{-1}\) を求めます．これは，\(\Theta(NM\log NM)\) 時間でできます．

以下では 2 変数 FPS の逆元を求める方法を 2 つ述べます． 2 変数 FPS の基本操作のパフォーマンスの良い アルゴリズムについて書かれている資料を知らないので，以下は私が今回独自に考えた内容です．

方法 1

1 変数の FPS でよくやられているのと同じ Newton 法（ダブリング）で，\((N,M)\) までの計算を \((2N,M)\) に延長するという手法をとれば，\(\Theta(NM\log NM)\) 時間で計算できます．

ntt の回数を節約するタイプの高速化チャンスが色々ありそうなので，突き詰めると結構考えることがありそうです．

方法 2

\(F(x,y)G(x,y) = 1\) のとき \(F(xy,y)G(xy,y)=1\) なので，\(F_1(x,y) = F(xy,y)\) の逆元を求めればよいです．\(F_1\) は上三角つまり，\(x^iy^j\) の係数が \(0\) でないならば \(i\leq j\) が成り立ちます．

上三角な 2 変数 FPS ということは，言い換えれば \(y^n\) の係数が \(x\) の \(n\) 次以下の多項式であるということです．\(n\) 次以下の多項式ということは，適当な評価点 \(x_0, x_1, \ldots, x_n\) を代入したときの値から復元できるということを意味します．

したがって，上三角な 2 変数 FPS \(F_1\) の逆元を求めるには次のようにすればよいです：

  • \(N+1\) 個の評価点 \(x_0, \ldots, x_{N}\) をとる．
  • \(F_1(x_i, y)\) は \(y\) の 1 変数 FPS である．これの逆元を求める．
  • \(j\) ごとに，\(N+1\) 個の組 \((x_i, [y^j]F_1(x_i, y)^{-1})\) を多項式補間して \(x\) の多項式を得る．これが \([y^j]F_1(x,y)^{-1}\) である．

多点評価・多項式補間については，その特殊ケースである NTT を用いてしまってよいです．NTT - friendly でない mod を用いている場合には，chirp-z 変換を使ってもよいですし，愚直な \(O(N^2)\) 時間での多点評価を使う（全体で 3 乗時間）ことも選択肢に入るかもしれません．

この方法は，1 変数 FPS のライブラリがある前提で，

  • 新規実装がかなり少量かつ簡潔である
  • log, exp, pow などでも全く同じ実装を使いまわせる

ところが優れていると思います．

なお私が今回 inv を実装した範囲では，下手な方法 1 は方法 2 と同程度．より丁寧に実装した方法 1 は方法 2 よりも2 割ほど高速でした．

投稿日時:
最終更新: