[多項式・形式的べき級数] 高速に計算できるものたち

2022.04.26

前提知識

上の 3 つの記事では、ほとんど他サイト等を参照せずに私の記事だけで解説を完結させるようにしていましたが、本記事については、この記事だけですべての議論が追えるということは意図していません。

解説はあまりしない or 簡単な一言解説のみ。ただしなるべく検索方法などが分かる形にはしようと心がけているので、そうなっていなさそうな場所があれば教えてください。

多項式・形式的べき級数関連で計算量を落とすテクニックの類を、なるべく一ヶ所にまとめておきたいと思い立って、とりあえず主に記憶を頼りに作成。何かあれば不定期更新していくと思います。更新コストを下げて、網羅度を高めることを目指したいため、並べる順番の整備とかはあまりしていません。

$p$ と書いたときには、係数が有理数（分母が $p$ と素）で、それを $\bmod p$ で求める問題を考えています。入力や出力の長さを断りなく $N$ と書くことがあります。

しばしば暗黙に $N < p$ を仮定しています（特に $\exp, \log$ を使う場合）。FFT / NTT のことを、FFT 表記で統一しています。

資料

スポンサーリンク

積（畳み込み）

$f$, $g$ の積を、$O(N\log N)$ 時間で計算できる。FFT。

いろいろな計算量改善の基礎。とはいえここがめちゃくちゃすごい。

$ 1 / f $

Newton 法で $O(N\log N)$ 時間。$[x^0]f\neq 0$ を仮定。特に、除算 $g/f$ も $g\cdot (1/f)$ とすることで $O(N\log N)$ 時間で計算できる。

$\log f$

$O(N\log N)$ 時間。$[x^0]f = 1$ および $N<p$ を仮定。

例えば $\log(1-f) = -\sum_{n=1}^{\infty} \frac{f^n}{n}$ と定義する。$\frac{1}{1-x} = \sum x^n$ を積分すると思うと覚えやすい。$\log(1+f)$ の形で定義する文献の方が多いか。

$\log(f)’ = f’/f$、$\log(fg) = \log f + \log g$ を満たす。したがって $f’/f$ を積分することで計算可能。

分母に $n$ があることから、$N > p$ では普通には扱えない。「$\mathbb{F}_p$ 係数形式的べき級数の log」というものは定義すらしていないということに。$N$ 次未満のみに注目した多項式環 $\mathbb{F}_p[x]/(x^N)$ で定義する、あるいは $\Q[[x]]$ で定義されていて、係数が $\mathbb{Z}_p$ に入るところ考察対象にしている、等と見なすなど。

$\exp f$

Newton 法で $O(N\log N)$ 時間。$[x^0]f = 0$ および $N< p$ を仮定。

$\exp f$ は、$\sum_{n=0}^{\infty} \frac{f^n}{n!}$ によって定まり、$(\exp f)’ = (\exp f) f’$ や $\exp(f+g) = \exp(f)\exp(g)$ を満たす。

$\exp, \log$ の代表的な利用

$\exp, \log$ は互いに逆関数である。これらを合わせて、

  • $\prod f_i = \exp(\sum \log f_i)$

という式変形により、総積やべき乗が高速化できる場合がある。これを利用するに際して、$f$ の定数項が $1$ でない場合には、次数をずらしたり定数倍して定数項が $1$ の場合に帰着する必要がある。

またこの種の議論ではやはり $N < p$ が前提となる。例えば定数項が $1$ の多項式 $f$ について、$f^p \equiv \exp(p\log f) \equiv \exp(0) \equiv 1\pmod{p}$ という議論は $p$ 次以上の係数も考えると誤り（結論も明らかにおかしい）。

べき乗

次の $f$, $n$ に対して $f^n$ が定義できて、$O(N\log N)$ 時間で計算可能（繰り返し $2$ 乗法よりも高速）。

  • $n$ が非負整数
  • $n$ が有理数で、分母が $p$ と素。$[x^0]f=1$ を仮定。

後者は $f^n = \exp (n\log f)$ と定義できて、$\exp, \log$ の性質から $f^{ab} = (f^a)^b, f^{a+b}=f^af^b$ が分かる。例えば $n=1/2$ として、$\sqrt{f}$ が定義できるが、計算はべき乗の特殊ケースとして扱うよりも sqrt 専用の実装した方が定数倍がよい。$[x^0]f \neq 1$ のときに $g^2 = f$ となる $g$ のことを $\sqrt{f}$ と書くことは、通常しないと思う。

疎な場合の高速化

$g$ の $0$ でない係数が $K$ 個であるとき、$fg$, $f/g$ が $O(NK)$ 時間で計算できる。後者は $[x^0]g \neq 0$ を仮定。

愚直にやればよい。コンテストでは結局これが問われているということも多い。

また、$f$ の $0$ でない係数が $K$ 個であるとき、次が $O(NK)$ 時間。

  • $1/f$
  • $\exp f$
  • $\log f$
  • $f^n$

$\log f$ は $f’/f$ を積分。$\exp f$ と $f^n$ は、微分を考えると係数の間の疎な漸化式が得られて、下から計算していく。より具体的には $F=e^f$ とすると $F’=Ff’$ であり、$F=f^n$ とすると $fF’=nFf’$ であることを利用する。

また $f$ が $d$ 次多項式で、計算結果の $N$ 次の係数にだけ興味がある場合、やはり同じ $F, F’$ の関係式から $F$ は P-recursive であることが分かるので、$O(\sqrt{N}\log Npoly(d))$ 時間で計算できる。

合成 $f(g(x))$

$g$ のべき乗を baby step, giant step に分ける平方分割で、$O(N^2)$ 時間などでできる。$O((N\log N)^{1.5})$ にもなるが、競プロ制約下では区別が困難か？Library checker の最速は $O(N^2)$ である（2022年4月現在）。

逆関数

$f$ を $[x^0] f = 0$ かつ $[x^1] f \neq 0$ となる形式的べき級数とする。$f(g(x)) = g(f(x)) = x$ となる $g$ を $f$ の逆関数という。$f$ の $N$ 次までが与えられているとき、$g$ の $N$ 次までを $O(N^2)$ や $O((N\log N)^{1.5})$ 時間でできる。$f(g(x)) – x = 0$ という方程式について Newton 法をすることを考えると、いろいろな $p(x)$ に対して合成 $f(p(x))$ や $f'(p(x))$ などが計算できればよくて、上の合成で述べた通りである。$1, 2, 4, \ldots, 2^k$ ($2^k\geq N$) の場合の合成を計算することになって、合成を $O(N^2)$ や $O((N\log N)^{1.5})$ 時間で行うことで、逆関数も同様の計算量で計算できる。

http://www.eecs.harvard.edu/~htk/publication/1978-jacm-brent-kung.pdf

この議論を踏まえると、$f(g(x))$ が $O(N\log N)$ 時間で求まるならば、$f$ の逆関数も $O(N\log N)$ 時間で求められることが分かる。

多項式の除算

多項式の余り付き除算と、形式的べき級数の除算は別ものであることに注意。多項式除算の商を求めることは、reverse して形式的べき級数の除算をすることに帰着できて、$O(N\log N)$ 時間でできる。

多項式の gcd

$O(N\log^2N)$ 時間。細かい議論や実装が結構大変。（概要だけ調べて自分で細部を考えようとしたが失敗しまくった。個人的には 2022年4月現在の Library Checker の 多項式・形式的べき級数まわりの問題で一番難しかった。）

$f^k \bmod g$

$f, g$ を $N$ 次多項式として、$O(N\log N\log k)$ 時間。多項式乗算・多項式除算ができるので、これを繰り返し $2$ 乗法に乗せればよい。

繰り返し $2$ 乗法にはよく知られたアルゴリズムが $2$ 種あるが、$f$ が疎である（$f$ との乗算が高速）場合などは、$f$ 倍と $2$ 乗に分解する再帰的な方法の方が定数倍がよい。例えば ARC 139 E の $(x+x^{-1})^M \bmod (1-x^N)$ の計算など。

$x^k \bmod f$

上述の通り $O(N\log N \log k)$ 時間でできるが、より定数倍がよい方法もある。

$f^k \bmod (1-x^N)$, $N$ は $ 2 $ べき

巡回畳み込み。FFT は、$\bmod 1-x^N$ での畳み込みを各点積に変えるという性質があって、この形の畳み込みは非常に扱いやすい。そもそも、多項式の積を FFT で求めるときにはこの性質を用いているのであった。

したがって、長さ $N$ の FFT をして、各点ごとに $k$ 乗してから iFFT すればよい。$O(N\log N + N\log k)$ 時間。

$N$ を一般化しようとすると、長さ $N$ の離散フーリエ変換を十分高速に行うことが課題となる。例えば $\mod p$ で $1$ の原始 $N$ 乗根がとれるならば、この方法が使えるということになる。

一般の $N$ だと、繰り返し $2$ 乗法で $O(N\log N\log k)$ 時間。

$N$ が小さければ、$O(N^2)$ 時間で愚直にフーリエ変換することも考えられる。次の問題は、複素数体で長さ $10$ 以下のフーリエ変換をする方法でも解ける。

分割の数え上げ (1)

$N$ 以下の整数の列 $A_1,\ldots, A_M$ に対して、$\prod (1 + x^A_i)$ や $\prod (1-x^{A_i})^{-1}$ の $N$ 次までが $O(M + N\log N)$ 時間で計算できる。

$\prod f_i = \exp(\sum \log f_i)$ を使う。$\log (1+x^{A_i})$ には $0$ でない係数が $N/A_i$ 個程度ある。各 $n$ に対して $A_i = n$ となる $i$ の個数を求めておけば、$\sum N/n \in O(N\log N)$ 時間で $\sum \log f_i$ を計算できる。

特に、$N$ 番目までの分割数が $O(N\log N)$ 時間で計算できる。が、分割数に関しては五角数定理と $1/f$ の計算を利用した方が定数倍がよい。

分割の数え上げ (2)

$A_1,\ldots, A_M$ が与えられていて $S = \sum A_i$ とするとき、$[x^N] \prod (1-x^{A_i})^{-1}$ が $O(SM\log N)$ 時間または $O(S\log S\log N)$ 時間。

有理式の係数 $[x^N] f/g$ に帰着されるが、Bostan-Mori をやっていこうとすると、$g(x)g(-x) = g(x^2)$ （$1-x^2=(1-x)(1+x)$ なので）より常に分母が変化しないというのがびっくりポイント。分子は $g$ と畳み込むことが必要だが、FFT で $O(S\log S)$ 時間、または疎な多項式の積に分解してひとつずつかければ $O(SM)$ 時間である。

桁 dp と見なすことでも、同様の $O(SM\log N)$ 時間の解法が得られる（出題者の解説）。同じ解法を形式的べき級数で考察しようとしたときの導出が面白かった。

多項式の総積

$f_1, \ldots, f_M$ を多項式として、次数の総和が $N$ であるとする。総積を $O(N\log^2 N)$ 時間で計算できる。分割統治すればこの計算量になる。

$f_i$ が低次だとしても $\log f_i$ が疎になるわけではないので、$\exp, \log$ による高速化は一般にはできない（$O(NM\log N)$ 時間になってしまう）。

なお、$1$ 次式を $2^N$ 個かけるという状況では、「$2^n$ 次の多項式を $2$ つかける」類の計算を繰り返すことになり、この多項式の次数の組合せは、$2$ べきの FFT による畳み込みのワーストケースを引き続ける。この場合、$(1+xf)(1+xg) = 1+x(f+g)+x^2fg$ などして計算すると、$2^n-1$ 次の多項式の積に帰着出来て定数倍が良くなる。

有理式の総和

$f_1, \ldots, f_M, g_1, \ldots, g_M$ を多項式として、次数の総和が $N$ であるとする。$f_i / g_i$ の和は、$N$ 次以下の多項式 $g, h$ を用いて $g/h$ と書ける。この $g, h$ が $O(N\log^2N)$ 時間で計算できる。やはり分割統治すればこの計算量になる。

$i$ 乗和の $i$ に関する列挙

$A_1, \ldots, A_N$ が与えられたとき、$\sum_n A_n^i$ を $i=0, 1, \ldots, N$ で列挙することが $O(N\log^2 N)$ 時間でできる。求めるべきは $\sum (1-A_ix)^{-1}$ であるが、これを有理式として計算したあとで、形式的べき級数除算をすればよい。

より定数倍がよい方法として、積分して $\sum \log (1-A_i x) = \log \prod(1-A_i x)$ の計算に帰着する。多項式の総積と $\log f$ の計算に帰着して $O(N\log^2N)$ 時間である。

基本対称式の列挙

$A_1, \ldots, A_N$ が与えられたとき、$d$ 次の基本対称式 $\sum_{i_1 < \cdots < i_d} \prod_j A_{i_j}$ の列挙が $O(N\log^2 N)$ 時間でできる。$\prod(1+A_ix)$ の計算をすればよいので、多項式の総積で述べた通り。

$f(x)f(rx)f(r^2x)…f(r^{n-1}x)$

$F(x) = f(x)f(rx)f(r^2x)\cdots f(r^{n-1}x)$ とすると、関数等式 $F(x) f(r^nx) = F(rx) f(x)$ が成り立つ。$f$ が疎ならば、ここから係数間の疎な関係式が得られて順番に計算できる。

特に、$\mathbb{F}_q$ ベクトル空間の部分空間の数え上げなどを多項式で考察すると、$(1-x)(1-qx)\cdots (1-q^Nx)$ のような形の式が出てくることがあるが、これは $O(N)$ 時間で展開できる。この計算結果は二項定理の $q$ 類似と見なすことができて（$q$-二項定理）、係数は Gauss の $q$-二項係数 と呼ばれる。

$f$ が密ならば、$\log, \exp$ を利用して $O(N\log N)$ 時間。

$F_n^k$ （Fibonacci 数列の $k$ 乗）が満たす線形漸化式

Fibonacci 数列に限らず、$3$ 項間漸化式を持つならば同様。

C-recursive な数列の積は C-recursive なので、特に $k$ 乗も C-recursive である。が、積の満たす線形漸化式を求めることはそれほど簡単ではない（一般な状況では、Berlekamp–Massey アルゴリズムを使うのがよいか？）。

$1-x-x^2 = (1-ax)(1-bx)$ となる $a, b$ をとって、以下 $a\neq b$ であるとする。$F_n$ は $a^n, b^n$ の線形結合であるから、$F_n^k$ は $a^k, a^{k-1}b, \ldots, ab^{k-1}, b^k$ の $n$ 乗の線形結合である。したがって、$F_n^k$ は $k+2$ 項間漸化式を持つことが分かる。その漸化式を復元するには、次の積を計算すればよい：$(1-a^kx)(1-a^{k-1}bx)\cdots (1-ab^{k-1}x)(1-b^kx)$.

これは上に述べた $(1-x)\cdots (1-q^N x)$ の計算と同じことになる。積を $f(x)$ とすれば、関数等式 $f(ax)(1-b^{k+1}x) = f(bx)(1-a^{k+1}x)$ から、隣接する係数の比が $a^n-b^n$ の形の数の比として計算できることがわかる。$(a^n-b^n)/(a-b)$ は元の $3$ 項間漸化式と同じ漸化式を満たすので、この比も順に計算できる。$a,b$ は $\Q$ や $\mathbb{F}_p$ の元としてとれるとは限らないが、そこも結局問題とならず、$(1-a^kx)(1-a^{k-1}bx)\cdots (1-b^kx)$ は $O(k)$ 時間で計算できる。

結局、係数は連続するフィボナッチ数の積の商で表され、Fibonacci 二項係数ということもあるらしい。

これができる出題例を聞いたことがあるが、紛失。$\sum_{n=0}^N F_n^k$ を $O(k\log k\log N)$ 時間で求めよとかかな。

Polynomial Taylor Shift

$O(N\log N)$ 時間。

特に、$\sum_n A_n\binom{n}{i}$ の $i$ に関する列挙ができる。

Bell 数

Bell 数とは、$n$ 個のものをグループに分ける方法の数え上げ。指数型母関数が $\exp(\exp x – 1)$ なので $O(N\log N)$ 時間で計算できる。

第 1 種 Stirling 数

符号なし第 $1$ 種 Stirling 数 $c(n,k)$ とは、$n$ 個のものを $k$ 個のサイクルに分ける方法の総数。したがって例えば $\sum_k c(n,k) = n!$ が成り立つ。これに適切な符号をつけたもの $s(n,k)$ を第 $1$ 種 Stirling 数と呼び分けることもある。

$\sum_k c(n,k)x^k = x(x+1)\cdots (x+n-1)$ である。$c(N,k)$ の $k$ に関する列挙が、分割統治をして、片側半分の計算を polynomial shift で再利用すると、$O(N\log N)$ 時間でできる。

下記の $\prod_{k} f(kx)$ を利用する別解法もある。reverse すると $\prod_{n=0}^{N-1} (1 + nx)$ の係数が $c(N, N – k)$ であることが分かるので、$k = 0, 1, \ldots, K$ に対する $c(N, N – k)$ の列挙が $O(K\log K)$ 時間でできる。この別解は巨大な $N$ に対しても $c(N, N-k)$ を列挙できるところが優れている。

$K$ を固定したときの $c(n, K)$ の $n$ に関する列挙もできる。$c(n,k)$ には $2$ 変数指数型母関数 $\sum_{n,k}c(n,k)t^k\frac{x^n}{n!} = (1-x)^{-t} = \exp t(-\log (1-x))$ がある。$K$ を固定して $t^K$ の係数を見ると $\sum_{n}\frac{c(n,K)}{n!} x^n = \frac{1}{K!}\bigl(-\log(1-x)\bigr)^K$ が得られるので、$c(n,K)$ の $n$ に関する列挙が形式的べき級数のべき乗を利用して $O((N-K)\log (N-K))$ 時間でできる。

第 2 種 Stirling 数

第 $2$ 種 Stirling 数 $S(n,k)$ とは、$n$ 個のものを $k$ 個の空でない部分集合に分ける方法の総数。したがって例えば $\sum_{k} S(n,k)$ は Bell 数に等しい。

包除原理などから $S(n,k) = \frac{1}{k!} \sum_{i=0}^k (-1)^{k-i}\binom{k}{i}i^n$ や $\sum_{n} S(n,k)\frac{x^n}{n!} = \frac{1}{k!}(e^x-1)^k$ が成り立つ。$S(N,k)$ の $k$ に関する列挙が前者の式と畳み込みで $O(N\log N)$ 時間でできる。$S(n,K)$ の $n$ に関する列挙は後者の式から $O((N-K)\log (N-K))$ 時間でできる。

$\sum A_i(x+a)^i(x+b)^{N-i}$

分割統治を考えると $O(N\log^2N)$ 時間だが、polynomial taylor shift をうまく使うと $O(N\log N)$ 時間になる。ARC133 F で参加者の提出から。

polynomial taylor shift をすると、$\sum A_i(x+a)^ix^{N-i}$ の形の計算に帰着できる。これは $x^N\sum A_i(1+ax^{-1})^i = x^N\sum a^iA_i (1/a + x^{-1})^i$ ということになるので、$\sum a^iA_ix^i$ を $1/a$ だけ shift してから reverse するような形でできる。

多点評価

簡単のため多項式の次数、評価点ともに $N$ 個とする。$N$ 次多項式を $M$ 個の点で評価する問題。

$O(N\log^2N)$ だが、評価点が等比数列の場合には $O(N\log N)$ 時間になる。

多項式補間

$N$ 次多項式および、$N+1$ 個の相異なる評価点での値 $(x_i, f(x_i))$ が与えられていて、$f$ の係数列を復元する問題。

$O(N\log^2N)$ だが、評価点が等比数列の場合には $O(N\log N)$ 時間になる。

多項式の評価点シフト

これも「多項式補間」というと個人的に思っていたが、わからなくなった。Library checker の問題名から評価点シフトとした。

$f$ が $N$ 次多項式であり、$f(0), \ldots, f(N)$ が与えられているとき、$f(a)$ が $O(N)$ 時間で計算できる。Lagrange 補間の式を考えて、評価点が等間隔であることを用いると、適当な列の区間積が求められればよいことが分かるので。

$M$ 個の点 $f(a), \ldots, f(a+M-1)$ で同時に評価することも、$O((N+M)\log(N+M))$ 時間あるいは、長さ $N$, $M$ の列を畳み込む時間でできる。

$f$ の係数列そのものは復元しない。この設定で $f$ の係数列が $o(N\log^2N)$ になるという話は聞いたことがない（ありますか？）。

$\sum_{n=0}^N n^k$

$O(k)$ 時間。

この総和は $N$ の $k+1$ 次多項式である。$N=0,1,\ldots,k+1$ の値を求めたあと、評価点シフトすればよい。$n^k$ の $n$ に関する列挙は、素数のところ（約 $k/\log k$ 個）を繰り返し $2$ 乗法で求めたあと、$(ap)^k=a^kp^k$ で補間すれば、全体として $O(k)$ 時間で行える。

なお、$\sum_{n=0}^N n^k = S_k(N)$ となる $k+1$ 次多項式 $S_k$ そのものが欲しい場合、Faulhaber の公式 により Bernoulli 数 の計算に帰着できる。Bernoulli 数を定義通りの形式的べき級数除算で列挙することで、$S_k$ を $O(k\log k)$ 時間で求められる。

答が多項式になると分かれば、小さいところを計算したあと評価点シフトすればよいというアイデアは、単純な $k$ 乗和以外でも利用可能である。例えば$\sum_{n=0}^N(3+4n+5n^2)^k$ なども $O(k\log k)$ 時間の前計算のもと、$N$ ごとに $O(k)$ 時間でできる。

$\sum_{n=0}^{N-1} n^k$ の $k$ に関する列挙

$N$ を固定したときに $\sum_{n=0}^{N-1} n^k$ を $k=0, 1, \ldots, K$ に対して列挙しよう。$\sum A_i^k$ の列挙が $O(N\log^2N)$ などの時間でできることは既に述べたが、その特殊ケースであるこちらはより高速にできる。

必要な和は $1 + e^x + e^{2x} + \cdots + e^{(N-1)x}$ の計算の係数から取り出せる。したがってこの和を計算すればよいが、等比数列の和なので $\frac{e^{Nx}-1}{e^x-1}$ と式変形をして、$O(K\log K)$ 時間でできる。分母の定数項が $0$ であるので、先に分子・分母を $x$ で割っておくことで形式的べき級数の除算の形になる。

$\sum_{k=L}^{R-1} f(kx)$ の計算

$\sum_{k=L}^{R-1} f(kx)$ の $N$ 次までが $O(N\log N)$ 時間で計算できる。

$n$ 次の係数を求めることを考えると、$\sum_{k=0}^{K-1}k^n$ が求められればよく、これは上述の通り $n=0,\ldots,N$ に対する列挙が可能である。

$\sum_{k=L}^{R-1} f(k^2x)$ なども同じようにできる。

$\prod_{k=L}^{R-1} f(kx)$ の計算

$\prod_{k=L}^{R-1} f(kx)$ の $N$ 次までが $O(N\log N)$ 時間で計算できる。$\exp, \log$ を用いて $\sum_{k=L}^{R-1} f(kx)$ を求める問題に帰着すればよい。

$[x^0]f \neq 1$ の場合に $\exp, \log$ を利用する議論を確認しておく。$f\neq 0$としてよく、$f(x) = cx^dg(x)$ となる $c\neq 0$, $d\geq 0$ および $[x^0]g=1$ となる $g$ がとれる。$\prod f(kx) = \prod c(kx)^d\cdot \prod g(kx)$ であるこのうち $\prod g(kx)$ は $\exp, \log$ で処理できる。

$\prod c(kx)^d = c^{R-L}x^{d(R-L)}\cdot (\prod k)^d$ であり、$\prod_{k=L}^{R-1} k$ の形の計算が必要そうに見える。しかし、$d=0$ ならばこの部分は計算不要である。$d>0$ ならば、$x^{d(R-L)}$ の項があるため $R-L > N$ の場合にはそもそも答が $0$ になる。結局 $\prod_{k=L}^{R-1} k$ の計算が必要なのは $R-L\leq N$ の場合だけであり、この部分は $O(N)$ 時間である。

分割の数え上げ (3)

$N$ を $1, 5, 10, 50, 100, 500$ に分割する方法の数え上げが、$N$ について定数時間でできる。

これは、分母が $(1-x)(1-x^5)(1-x^{10})(1-x^{50})(1-x^{100})(1-x^{500})$ の有理式の係数を求める問題である。この分母の倍数として、$(1-x^{500})^6$ がとれるから、答は $f / (1-x^{500})^6$ の形の有理式の係数列である。特に、$500$ 項ごとに見て $5$ 次多項式の規則がある。したがって、事前に $3000$ 次まで係数を求めておけば、$5$ 次多項式の評価点シフトに帰着できる。

$\sum_{n=0}^N n^kr^n$, $\sum_{n=0}^{\infty} n^kr^n$,

まず、$n^kr^n$ という数列は、$f / (1-rx)^{k+1}$ の形の有理式を母関数に持つ。したがってその累積和は $f / (1-x)(1-rx)^{k+1}$ の形の有理式を母関数に持つ。$r=1$ ならば係数列は多項式なので、評価点シフトに帰着できる。以下 $r\neq 1$ とする。

$f / (1-x)(1-rx)^{k+1} = c/(1-x) + g / (1-rx)^{k+1}$ （$c$ は定数、$g$ は $k$ 次以下）という部分分数分解を考える。$(1-rx)^{k+1}$ をかけたときの $k+1$ 次の係数を見ることで $c$ が復元できる（係数ひとつ得るだけなので畳み込む必要はなく、$c$ は $O(k)$ 時間で手に入る）。$f, g$ は陽に復元せず、有理式の先頭 $k+1$ 項を扱う。

結局、$[x^N] g(x)/(1-rx)^{k+1}$ の計算に帰着されるが、この計算結果は $r^N$ と多項式の積であるから、多項式の評価点シフトに帰着できる。

この理解に基づくと、次の問題の方が簡単である。$g / (1-rx)^{k+1}$ の係数は $r^N$ と多項式の積なので $0$ に収束して、部分分数分解の $c$ が答である。

$[x^M]1/(1-x-x^2)(1-x)^N$

単に線形漸化式補間だと思うと $O(N\log N\log M)$ 時間であるが、これも $(a+bx)/(1-x-x^2) + f / (1-x)^N$ の形の部分分数分解を考えると、$3$ 項間漸化式の補間と多項式補間に分解できて、$O(N + \log M)$ 時間で解ける。

この問題のユーザー解説を書いた当時は $a, b, f$ をすべて求める考察をしたが、上の問題と同様に $a,b$ だけ復元する方が考察は簡潔か。$(1-x)^N$ をかけたときの $N, N+1$ 次の係数を計算することで、 $a, b$ が復元できる。

relaxed multiplication

$h = fg$ があり、$i=0, 1, \ldots, $ の順に次を行うことが $O(N\log^2N)$ 時間でできます。

  • $i$ について昇順に次を行う：$[x^i] f$, $[x^i] g$ が与えられるので、$[x^i] h$ を求める。

$[x^i]h$ を求めるまで $[x^{i+1}]f$, $[x^{i+1}]g$ が与えられないという制限があります。

分割統治の要領で、$O(N\log^2N)$ 時間で $h$ を計算できます。

例えば $f = (xf + …)g$ や $f’ = (f + …) g$ のように、両辺に同じ未知数 $f$ がある方程式ができたときに利用できます。

$\prod_{i}(a_ix+b_i)^{c_i}$

$M$ 個の $1$ 次式のべき乗の積 $\prod_{i}(a_i+b_ix)^{c_i}$ を $N$ 次まで求めることが、$O(M\log^2M + N\log N)$ 時間でできる。

まず、$a_i=0$ の場合と定数倍を適切に扱うことで $a_i = 1$ の場合 $\prod_{i}(1+b_ix)^{c_i}$ に帰着しておく。$F = \prod_{i}(1+b_ix)^{c_i}$ としたとき

$$(\log F)’ = \sum_i \frac{b_ic_i}{1+b_ix}$$

が成り立つ。右辺は有理式としての分子・分母が $O(M\log^2M)$ 時間で計算できる。その $N$ 次までを $O(N\log N)$ 時間で求められる。それを積分して $\exp$ すればよい。

より一般に、低次の多項式・有理式のべき乗の総積という状況で同じことができる。

$\sum_{i}a_i \exp(b_ix)$

$M$ 個の $\exp(bx)$ の線形結合 $\sum_{i}a_i \exp(b_ix)$ の $N$ 次までを求めることが、$O(M\log^2M + N\log N)$ 時間でできる。

$\exp(bx) = \sum_{n} \frac{b^n}{n!}x^n$ が、係数ごとの $n!$ 倍により $\sum_{n} b^nx^n = \frac{1}{1-bx}$ に対応することを利用する。結局 $\frac{a_i}{1-b_ix}$ を計算したあと係数ごとに $n!$ で割ればよい。有理式としての分子・分母が $O(M\log^2M)$ 時間で計算できるので、その $N$ 次までを除算すればよい。

$b_i$ が小さな非負整数の場合には、多項式 $f$ に対して $f(\exp x)$ を計算できたという見方もできる。

疎な微分方程式

$a(x), b(x)$ が疎な形式的べき級数とし、$[x^0]a=1$ を満たすとする。このとき、$1$ 階線形微分方程式

$$a(x)F'(x) + b(x)F(x) = 0,\qquad [x^0]F=1$$

の解が一意存在し、$O(NK)$ 時間で求められる（$K$ は $a,b$ の非零項の個数）。係数を $a_i, b_j$ などと書くことにして、実際、$[x^n]$ の条件を考えると

$$\sum_i a_i(n-i+1)F_{n-i+1} + \sum_j b_jF_{n-j} = 0$$

となり、左辺は $a_0(n+1)F_{n+1}$ および $F_n$ までから計算できる値からなるので順に計算できる。

疎な場合の高速化 (2)

$f, g$ が疎な形式的べき級数で、非零項が $K_1, K_2$ 個であるとする。簡単のため $[x^0]f=[x^0]g=1$ とする。このとき $f^ng^m$ や $\exp(f/g)$ などの計算が、$O(NK_1K_2)$ 時間でできる。

まず、$F = f^ng^m$ は、$\log F = n\log f + m\log g$ より $\frac{F’}{F} = \frac{nf’}{f} + \frac{mg’}{g}$ から $F$ についての疎な線形微分方程式が得られる。

例えば、$f^ng^m$ の $n, m$ は負でもよい。例えば $\frac{(x+x^2)^{N}}{(1-x^3)^N}$ が線形時間で計算できる（https://atcoder.jp/contests/abc276/tasks/abc276_g）。

$F = \exp(f/g)$ も、$\log F = f/g$, $\frac{F’}{F} = \frac{f’g-fg’}{g^2}$ より同様である。

$fgF$ などを $gF$, $g’F$ などを介してこれらの計算量を $O(N(K_1+K_2))$ にすることも可能である：

スポンサーリンク
タイトルとURLをコピーしました