形式的冪級数に関する一階常微分方程式を解く

最近話題の形式的冪級数 (FPS) です。最近と言いつつ 4 年くらい前から流行り始めていた気がします。当時は「母関数」と呼んでいる人が多かった気がします。

今回は、FPS で考察をしていて「$\frac{\dd}{\dd x}y = f(y)$ なる FPS $y(x)$ に対して $y(x)\bmod x^n$ を求めたいな〜」となったときの話をします。

å°Žå…¥

たとえば、考察の結果、求めたい $y$ が $y^2 + 2xyy' - y' = 0$, $y(0) = 1$ となるらしいことがわかったとします*1。

出処

これは Catalan 数です。$C(x) = 1 + xC(x)^2$ なので、$y = 1 + xy^2$ で、$y' = y^2 + 2xyy'$ です。

こういうときは Wolfram|Alpha 大先生に聞けばいいですね。

www.wolframalpha.com

y^2 + 2xyy' - y' = 0, y(0) = 1

$$y(x) = - \frac{\sqrt{1-4x}-1}{2x}$$

と答えてくれたのでこれを求めればいいですね、おわりです（？？？）。

それでもいいのですが、「実際に $y(x)$ を陽に求めて、その FPS を求める」というステップを踏まずに求める方法の紹介です。 やる必要があることとしては、

• 考察ステップで $y' = f(y)$ なる $f(y)$ を求めておく
• 多項式 $y$ と整数 $n$ に対する関数 $(y, n) \mapsto f(y) \bmod x^n$ を実装する
• 多項式 $y$ と整数 $n$ に対する関数 $(y, n) \mapsto \frac{\dd}{\dd y} f(y) \bmod x^n$ を実装する

上記の例であれば、$f(y) = y^2\cdot(1-2xy)^{-1}$ と $\frac{\dd}{\dd y} f(y) = 2y(1-xy)\cdot(1-2xy)^{-2}$ です*2。

$f(y) \bmod x^n$ と $\frac{\dd}{\dd y} f(y) \bmod x^n$ を求めるための計算量を $F(n)$、長さ $n$ の畳み込みの計算量を $M(n)$ とすると、全体で $O(F(n)+M(n))$ 時間で計算できます。よくある設定だと $O(n\log(n))$ とかでしょうか。

解説

ここに書きました。

rsk0315.github.io

fode という名前は first-order ordinary differential equation から来ていると思います。リンク先の References にある論文（“Series solutions of algebraic and differential equations: a comparison of linear and quadratic algebraic convergence” の方）から拝借しました。

問題例

yukicoder.me

ネタバレを含みます

解説を読むと、$S'(x) = S^2(x) + 1$ および $T'(x) = T(x)\tan(x)$ を満たす $S(x)$, $T(x)$ を求めるらしいことがわかります。初期条件は $S(0) = 0$, $T(0) = 1$ です。

$f(S) = S^2+1$, $g(T) = T\tan(x)$ とすると、$\frac{\dd}{\dd S} f(S) = 2S$ と $\frac{\dd}{\dd T} g(T) = \tan(x)$ とわかるので、上記を実装すればよいです。

$\tan(f(x))$ の FPS も Newton 法で求められます。あるいは、ここでは $\tan(x)$ さえ計算すればよいので、有名な $\sin(x) = \frac{x^1}{1!} - \frac{x^3}{3!} + \cdots$ と $\cos(x) = \frac{x^0}{0!} - \frac{x^2}{2!} + \cdots$ から $\sin(x)\cdot \cos(x)^{-1}$ として求めてもよいでしょう。

Note: より一般には、与えられた $f(x)$, $g(x)$ に対して $e^{f(x)+ig(x)} = u(x)+iv(x)$ の形式の $u(x)$, $v(x)$ を求められるらしいので、$u(x) = \cos(g(x))$, $v(x) = \sin(g(x))$ などとなり、$\tan(g(x)) = u(x)\cdot v(x)^{-1}$ のようになるでしょう。

所感

微分方程式を手や手以外で解きさえすれば使わずに済むので、あまり必要ないかもしれません。 微分方程式を解くための Newton 法の中で、$\exp$ の計算（Newton 法を使う）や逆元の計算（Newton 法を使う）や、積の計算（FFT を使う）などを行っている関係で、定数倍が重くなってしまいます。 あるいは Catalan 数の例のように、一般項を手で出しておけば $O(n)$ 時間で解ける場合もあるので、オーダーレベルでの妥協になることもあります。

とはいえ、手で極値を求めずに三分探索で済ませるやつ のように、うまく使える場面もあるかもしれません*3。

補足

Catalan 数の例では、$y = 1 + xy^2$ から $f(y) \triangleq xy^2 - y + 1 = 0$ という方程式を解く方針もあります。これも Newton 法によって求めることができます。下記に書きました。

rsk0315.github.io

環 $R$ 上の多項式 $\varphi\in R[x]$ に関する Taylor 展開や微分積分などは、（解析の文脈でやるような）極限操作を介さずに定義されます。

きもち

不定元の扱い方だったり環の性質だったりは、競プロ er があまり慣れていない分野だと思うので、適宜勉強が必要な気がします（競プロ er が知っている代数的構造はモノイドだけなので*4）。 たとえばイデアルやカーネルのような用語を聞いただけで「こわ...」となってしまうタイプの人もいます。

「初心者向け解説なので」のようなフレーズで自分の知らないパートを誤魔化したり嘘を言ったりせずに、ちゃんと扱えるようになりたいですね。 怪しい FPS 解説記事が巷に溢れてお気持ち表明するえびちゃんを見たいです*5。怪しい記事が溢れなくても怪しい理解者はたくさんいるのかもしれません。やや可視化されにくそうです。

それはそれとして、問題を FPS で記述するパートができなければコンテスト本番で役に立たないんですよね、かなしいです。 そういう部分はどうやって練習するのがよいのでしょう。慣れれば実家らしいと聞くのですが。 LIFT だったり $\frac{\partial}{\partial y} f(x, y)\big|_{y=1}$ だったりみたいな話は知っているのですが、あまりちゃんと使えていません。relaxed multiplication はこれから知ります。 とはいえ、そういうのを知らないと「これに持っていけば解ける」というのがわからないので難しそうです。モノイドのことを知らずにセグ木の問題を解こうとするみたいな。

テクニック関連は Codeforces のブログ とかを読むとよいのでしょうか。

おわり

PAST も FPS で溢れるようになって「こんなの業務で使わないし PAST は役に立たない」とか言われるようになったり、いつの間にか業務でも当然 FPS が使われるようになったり、そういう未来もあるのでしょうか。

*1:FPS の文脈だと代入の形ではなく $[x^0] y(x) = 1$ のように書く方が一般的でしょうか。

*2:$x^n$ を法としたときの $f(x)$ の乗法逆元 $f(x)^{-1}$ は、Newton 法で $O(M(n) )$ 時間で求められます。$M(n)$ は長さ $n$ の畳み込みにかかる時間で、$O(n\log(n) )$ などです。

*3:三分探索は大枠の名前であって、三等分にするやつや黄金比で分けるやつたちの総称であるという立場を取っています（予防線（？））。

*4:そんなことはないらしいです。

*5:でも FPS 解説記事は maspy さんや Nyaan さんなどのものがあるので不要そうです。