polynomial_techniques.html

<!-- 数学ガチ勢の方、そうでない方も、指摘・加筆お願いします！ -->
<title>多項式を使うテクニックたち</title>
<p>注意：yukicoderやその他のサイトの問題に対するネタバレがある可能性があります</p>
<p>以下では多項式は可換環である$R$を係数とするとする。
計算量は$R$上の基本演算が定数時間でできるとして考える。ただしあまり厳密ではない。
競技プログラミングにおいてはたいていワードサイズのmodを取るので定数時間で計算できるとして問題ない事が多い。
</p>
<p>
多項式同士の乗算の計算量を$M(n)$とする。多項式除算も$O(M(n))$で計算できる。
単純なアルゴリズムでは$M(n) \in O(n^2)$だが、$R = {\mathbb Z}/m{\mathbb Z}$の場合はFFTを用いることで$M(n) \in O(n \log n \log \log n)$にできる。
</p>
<h3>多項式の総和</h3>
<p>
$p$を$k$次の多項式とするとき、$P(n) = \sum_{i=0}^{n-1} p(i)$は$k+1$次以下の多項式となる。
$\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}$などの公式として有名だろう。
</p>
<h3>多項式のある種の逆元</h3>
<p>
有名なpower seriesの式$\sum_{i=0}^{\infty} a^i = \frac{1}{1-a}$は多項式にも適用できる。
つまり、多項式$f = \sum_{i=0}^k a_i X^i$に対し、ある種の逆元を$\sum_{i=0}^{\infty} (1-f)^i$と表すことができる。
この式は$a_0 = 1$である場合に限りよく定義でき、これは多項式環の拡張である"formal power series"環上に値を取る。
</p>
<p>
$f$に$a_0^{-1}$かけることで、つまり$f^{-1} = a_0^{-1} \sum_{i=0}^{\infty} (1 - a_0^{-1} f)^i$として、$a_0 \in R^*$である限りこれを求めることができる。
</p>


<h3>多項式の平行移動</h3>
$f(X):=\sum_{i=0}^N a_iX^i$を$C$だけ平行移動した$f(X+C)$の係数を$O(N\log{N})$で求める。二項展開して地道に計算することで
$$
\begin{align}
f(X+C)=&\sum_{i=0}^N a_i (X+C)^i \\
      =&\sum_{i=0}^N a_i \sum_{j=0}^i \binom{i}{j}X^jC^{i-j}\\
      =&\sum_{i=0}^N X^i \sum_{j=i}^N a_j \binom{j}{i} C^{j-i}\\
      =&\sum_{i=0}^N \frac{X^i}{i!} \sum_{j=i}^N a_j \frac{j!}{(j-i)!} C^{j-i}\\
      =&\sum_{i=0}^N \frac{X^i}{i!} \sum_{k=0}^{N-i} a_{k+i}(k+i)! \frac{C^{k}}{k!} \\
      =&\sum_{i=0}^N \frac{X^i}{i!} [s^{-i}] g(s)\exp(Cs) \\
\end{align}
$$
を得る。ただし$g(s):=\sum_{i=0}^N a_i i! s^{-i},\exp(Cs):=\sum_{i=0}^N \frac{(Cs)^{i}}{i!}$とする。$g(s)$と$\exp(Cs)$の畳み込みになっているのでFFTで$O(N\log{N})$で計算できる。
これは平行移動後の関数をラプラス変換したものの逆ラプラス変換$\Theta(X+C) \sum_{k=0}^N f_k (X+C)^k = \mathcal{L}^{-1}[\exp(Cs)\sum_{k=0}^N a_k\frac{k!}{s^{k+1}}]$を計算しているとみなせる(?)。


<h3>$\Pi_{i=1}^{N}  (1+X^{s_i})$</h3>
分割数を計算するときに$\Pi_{i=1}^{N}  (1+X^{s_i})$を計算したくなることがある。
<a href="https://arxiv.org/abs/1807.11597">https://arxiv.org/abs/1807.11597</a>にて
$A(X):=\Pi_{i=1}^{N}  (1+X^{s_i}) \bmod X^{t+1}$を$O(t\log t)$で求めるアルゴリズムが示されている。
$\log(1+X)=\sum_{i=1}^\infty \frac{(-1)^{i-1}}{i}X^i$であるから
$$
\begin{align}
\log\Pi_{i=1}^{N}  (1+X^{s_i})=&\sum_{i=1}^N\log(1+X^{s_i}) \bmod X^{t+1}\\
=&\sum_{i=1}^N\sum_{j=1}^\infty \frac{(-1)^{j-1}}{j}X^{js_i} \bmod X^{t+1}\\
=&\sum_{i=1}^t \sum_{j=1}^{[t/j]} a_i\frac{(-1)^{j-1}}{j}X^{j i} \bmod X^{t+1}
\end{align}
$$
ただし、$a_i:=\#\{j:s_j=i\}$とする。$O(\sum_{j=1}^{t}[t/j])=O(t\log t)$で計算できる。あとは$A(X)=\exp(\log(A(X))$から計算すればよい。
<br>
演習問題<br>
<ul>
<li>AGC041-D (<a href="http://q.c.titech.ac.jp/docs/progs/AGC041D.html">Ryuhei_Moriさんの解説</a>)<br></li>
<li>EDPC-M (<a href="https://maspypy.com/%e5%a4%9a%e9%a0%85%e5%bc%8f%e3%83%bb%e5%bd%a2%e5%bc%8f%e7%9a%84%e3%81%b9%e3%81%8d%e7%b4%9a%e6%95%b0%ef%bc%88%ef%bc%92%ef%bc%89%e5%bc%8f%e5%a4%89%e5%bd%a2%e3%81%ab%e3%82%88%e3%82%8b%e8%a7%a3%e6%b3%95">maspyさんの解説</a>)<br></li>
</ul>
<h3>母関数</h3>
<p>
数列に対し、有理関数が母関数であることと線形漸化式であることは同値である。<br>
<!--とりあえず書いてみたので間違いなどあれば修正お願いします-->
・線形漸化式⇒母関数は有理関数<br>
数列$\{a_{n}\}_{n \geq 0}$が$n \geq M$のとき漸化式$a_{n}=\sum_{k=1}^{m}α_{k}a_{n−k}$ で表されているとする。（ただし$α_{k}$は定数かつ$\alpha_m \neq 0$）<br>
<!--α_{k}がnに依存する場合や、非斉次の場合は必ずしも成立しません-->
このとき母関数を$f$として $h(x):=1-\sum_{k=1}^{m}α_{k}x^{k} , g:=hf$とする。<br>
$g$の各次数の係数について考えれば、$M$次以上は全て相殺されるので$g$は高々$M-1$次多項式。<br>
$h$は定義より明らかに$m$次多項式なので$f=g/h$は有理関数。<br>
・母関数が有理関数⇒線形漸化式<br>
<!--以下の議論ではマクローリン展開を用いているため、実数体(または複素数体)上での議論となります-->
有理関数$f$を母関数とする数列$\{a_{n}\}_{n \geq 0}$を考える。<br>
$f$は有理関数なので多項式$g,h$により$f=g/h$と表せる。<br>
$hf=g$の両辺を$n(>\max\{\deg~g,\deg~h\})$回微分するとライプニッツ則により<br>
$\sum_{k=0}^{\deg~h}\binom nk f^{(n-k)}(x)h^{(k)}(x)=0$　（$\binom nk$は二項係数）<br>
となるので$x=0$を代入し、$k=0$の項を残して移項すると<br>
$f^{(n)}(0)h(0)=-\sum_{k=1}^{\deg~h}\binom nk f^{(n-k)}(0)h^{(k)}(0)$<br>
両辺を$h(0)n!$で割り、$f$のマクローリン展開により$a_{n}=f^{(n)}(0)/n!$であることを用いると<br>
$a_{n}=-\sum_{k=1}^{\deg~h}h^{(k)}(0)/h(0)/k!*a_{n-k}$<br>
ここで$h^{(k)}(0)/h(0)/k!$は$n$に依らない定数であるから、これは$(\deg~h)+1$項間線形漸化式である<br>
<!--一般の環Rについては、次の命題が示せれば十分であることまではわかりましたが、示せませんでした
命題 ∀f∈R[[x]].((∃g,h∈R[x].hf=g)⇒(∃g',h'∈R[x].(h'f=g' ∧ h'(0)∈A^*)))
「形式的べき級数がある有理関数と等しいなら、その分子分母を適当に取り替える事によって、分母の定数項を単元にできる」という意味です
これが言えれば、前半の議論をほぼそのまま逆にたどることで後半が示せます-->

</p>
<h3>多項式で表せるDP</h3>
<p>
以下の問題を考える：
「正整数の列$a$が与えられるとき、$a$の重複なし部分和でちょうど$b$になるものは何通りあるか？」
この問題は典型的なDPであるが、以下のように多項式によって表せる：
「$f = \prod_i (1+X^{a_i})$とするとき、$f$の$b$次の係数を求めよ」
この多項式はこの問題に関する母関数であるとも考えられる。
</p><p>
また、同じように、「正整数の列$a$が与えられるとき、$a$の重複あり部分和でちょうど$b$になるものは何通りあるか？」という問題の場合、
$f = \prod_i \sum_{j=0}^{\infty} X^{j a_i}$となるが、逆元を用いて$f = \prod_i (1-X^{a_i})^{-1}$とも表せる。
</p>
<p>多次元のDPであっても多変数多項式によって表せ、同じように考えられる。</p>
<h3>"戻すDP"</h3>
<p>
典型的な部分和数え上げ問題のDPの遷移が多項式の掛け算として表せることがわかった。
ならば、その逆演算である割り算がどう適用できるかを考えてみるのは自然だろう。
</p><p>
たとえば、$f = \prod_i (1+X^{a_i})$である場合、$(1+X^{a_i})$で割ることでDPを"戻す"ことができる。
つまり、$a$から要素$a_i$を削除した列でのDP結果が得られる。
実際には、$(1+X^{a_i})^{-1} = \sum_{j=0}^{\infty} (-X)^{a_i j}$となる。
単純に再計算する場合$O(nb)$程度の計算量がかかるが、この場合重複あり部分和DPと同じように実装することで$O(b)$の計算量で求めることができる。
</p><p>
重複ありの場合、$f = \prod_i (1-X^{a_i})^{-1}$であるが、
$((1-X^{a_i})^{-1})^{-1} = 1-X^{a_i}$というようにそれ自身であるので、"戻す"場合は重複なしDPのような掛け算によって実装できる。
</p>
<h4>関連する問題</h4>
<ul>
<li><a href='http://community.topcoder.com/stat?c=problem_statement&pm=11026'>TopCoder Member SRM 478 Div1 Hard "RandomApple"</a></li>
<li><a href='http://yukicoder.me/problems/183'>yukicoder No.155 "生放送とBGM"</a></li>
<li><a href='http://arc028.contest.atcoder.jp/tasks/arc028_4'>AtCoder Regular Contest 028 D "注文の多い高橋商店"</a>
    $\sum_{j=0}^{a_i} X^j = (1-X^{a_i+1}) (1-X)^{-1}$と変換できる。
</li>
</ul>
<h3>線形漸化式の値</h3>
<p>
$b_i = a_i (i < k), b_{i+k} = \sum_{j=0}^{k-1} c_j b_{i+j}$と表される線形漸化式を考える。
$f = X^k - \sum_{i=0}^{k-1} c_i X^i$とし、$X^j \bmod f = \sum_{i=0}^{k-1} d_i X^i$と表されたとすると、$b_j = \sum_{i=0}^{k-1} a_i d_i$となる。
これを繰り返し二乗法により計算すれば、線形漸化式のj番目の値を、$O(k^2 \log j)$または$O(M(k) \log j)$程度の計算量で解くことができる。
</p>
<h4>関連する問題</h4>
<ul>
<li><a href='http://abc009.contest.atcoder.jp/tasks/abc009_4'>AtCoder Beginner Contest #009 D "漸化式"</a></li>
<li><a href='http://tdpc.contest.atcoder.jp/tasks/tdpc_fibonacci'>AtCoder Typical DP Contest T "フィボナッチ"</a></li>
</ul>
<h3>多項式補間</h3>
<p>
$f(x_i) = y_i$となるような長さ$k$の列$x, y$が与えられているとする。$i \neq j$なら$x_i \neq x_j$とする。"多項式補間"では、この列から多項式$f$を復元する。
$f \bmod (X-a) = f(a)$である(Polynomial remainder theorem)。
つまり、解きたい式は連立1次合同方程式$f \bmod (X-x_i) = y_i$となる。これを解くには"中国人剰余定理"が適用できる。
$x_i \neq x_j$なら$\gcd(X-x_i,X-x_j) = 1$であることに注意すると、$f \equiv g \pmod{\prod_i (X-x_i)}$となるような$g$が得られる。
$R$が体なら次数$k$未満の多項式でユニークであるので、復元できたといえる。
中国人剰余定理の実装によってそれぞれ"ラグランジュ補間"や"ニュートン補間"が導出できる。
</p>
<p>
通常$O(n^2)$程度の計算量で補間できるが、等差数列に対してはほぼ線形時間の計算量で補間できる。
また、高速な多項式乗算のアルゴリズムを使って分割統治法方法を行うと$O(M(n) \log n)$程度の計算量で補間多項式が計算できる。
<!-- 後述のDFTも特殊な数列に対しての補間である。 -->
</p>
<p>
時々、答えの数列が多項式であることはわかっていても実際の多項式を求めるのは難しかったり計算量がかかってしまうことがある。
このとき、適当な数たちに対して、多項式でなく$R$上で計算をして、その後に多項式補間をすることで計算量が改善することがある。
</p>
<h4>関連する問題</h4>
<ul>
<li><a href='http://arc033.contest.atcoder.jp/tasks/arc033_4'>AtCoder Regular Contest 033 D "見たことのない多項式"</a></li>
<li><a href='http://yukicoder.me/problems/22'>yukicoder No.42 "貯金箱の溜息"</a></li>
<li><a href='http://community.topcoder.com/stat?c=problem_statement&pm=13369&rd=16058'>TopCoder TCO14 Round 3B Hard "TreeDistance"</a></li>
</ul>
<h3>彩色多項式</h3>
<p>
ある無向グラフ$G = (V,E)$に対し、$f(c)$を、このグラフを$c$色以下でproper彩色する場合の数、と定義する。
このとき、$f$は次数$|V|$以下の多項式となっている。
</p><p>
一般のグラフに対して求めるのは難しいが、木やchordal graph, cographなどの特殊なグラフクラスでは効率的に求めることができる。
</p>
<h4>関連する問題</h4>
<ul>
<li><a href='https://www.hackerrank.com/contests/codesprint5/challenges/coloring-grid'>HackerRank CodeSprint 5 "Coloring Grid"</a></li>
<li><a href='http://hos.ac/contest/xmas2012/'>Xmas Contest 2012 Problem C "Colorful Lights"</a></li>
<li><a href='https://judge.npca.jp/problems/view/174'>NPCA Judge #174 "木上のパスの塗り分け"</a> (自作問題)</li>
</ul>
<!-- どうも微妙なのでとりあえずコメントアウト
<h3>DFT</h3>
<p>
"DFT" (Discrete Fourier Transform), "NTT" (Number Theoretic Transform) より一般に "z-transform"は、ある特別な数列による多項式の多点評価と多項式補間であるとみなせる。
こう考えれば掛け算の準同型性による畳み込みも理解できる。
</p>
<h3>多項式の剰余環による拡張</h3>
<p>
複素数体$\mathbb C$は実数体$\mathbb R$を多項式$X^2 + 1$によって拡張したもの(${\mathbb C} \cong {\mathbb R}[X]/(X^2 + 1)$)であると考えられる。
同様に、ガウス整数は整数に対しての同じことである。${\mathbb Z}/m{\mathbb Z}$に対しても同じことを考えられる。
</p><p>
他には、例えば$f = X^2 - 5$によって拡張することで$\sqrt 5$が存在することになるので、フィボナッチ数のBinet's formulaを計算することができる。
(加筆求む)
</p>
<h4>関連する問題</h4>
<ul>
<li><a href='http://yukicoder.me/problems/370'>yukicoder No.147 "試験監督（2）"</a> フィボナッチ数を計算するだけの練習問題として。</li>    
<li><a href='https://www.hackerrank.com/contests/infinitum8/challenges/down-the-rabbit-hole'>HackerRank Ad Infinitum 8 "Down the Rabbit Hole"</a></li>
</ul>
-->
<h3>Polynomial Identity Test</h3>
<p>
<a href='http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma'>Schwartz–Zippel lemma</a>。
様々な乱択アルゴリズムにおいて重要な役割を果たしている。(加筆求む)
</p>
<h3>多項式ハッシュ</h3>
<p>
長さ$m$の文字列$S$と適当な関数$ord$に対し、多項式$f_S(X) = \sum_{i=0}^{m-1} ord(S_{m-i}) X^i$が定義できる。
これを適当な素数$p$で割った余りを取るとすると$f$はハッシュ関数の族となる。
ただし、$c \neq d$に対して$ord(c) \not\equiv ord(d) \pmod{p}$であり、$ord(c) \not\equiv 0 \pmod{p}$である必要がある。
2つの文字列$S, T (|S| = m, |T| = n)$に対して、ランダムな$B$に対して$f_S(B) \equiv f_T(B) \pmod{p}$となる確率は$\frac{\max(m,n)}{p}$で抑えられる。
</p>
<p>
このハッシュ関数はハッシュ値のまま様々な操作ができる点で有用である。
例えば、$f_{S T} = X^n f_S + f_T$のようにして文字列連結ができる。
特に文字$c$に対して、$f_{S c} = X f_S + ord(c)$である。
また、$S$の接頭詞$S[1,i)$に対するハッシュを事前計算しておくことによって、$f_{S[i,j)} = f_{S[1,j)} - X^{j-i} f_{S[1,i)}$として部分文字列のハッシュ値を計算できる。
</p>
<p>
応用は多岐に渡り、文字列検索・LCPの計算など様々なことに利用できる。
多次元にも拡張でき、その場合は多変数多項式になる。
ただし、安易な利用による衝突に関しては、別に記事が必要なほどに落とし穴にはまりやすいので注意すること。
</p>
<h4>関連する問題</h4>
<ul>
<li><a href='http://codeforces.com/contest/514/problem/C'>Codeforces Round #291 (Div. 2) C "Watto and Mechanism"</a></li>    
</ul>