因数分解と多項式の $n$ 項目の計算

多項式の $n$ 項目を計算する際、因数分解することで計算量が改善することがある。

次の例1, 2は maspy さんのブログと ABC240G から取っているので詳しい解説はそちらを参照してほしい。

任意の座標 $(x,y)$ から $(x \pm 1, y), (x, y \pm 1)$ に移動できる。$(0,0)$ から $(X,Y)$ に $N$ 回の移動で到達する方法は何通りあるか。（出典:maspyさんブログ）

求める値は
\begin{align}
&[x^Xy^Y](x+x^{-1}+y+y^{-1})^N \\
=& [x^{X+N}y^{Y+N}](1+xy)^N(x+y)^N
\end{align}として表される。展開して $x^{X+N}y^{Y+N}$ となるものを列挙するには、$1,xy,x,y$ を選ぶ回数を表す変数 $4$ つについて、$1,xy$ を選んだ回数の和と $x,y$ を選んだ回数の和が $N$ に等しいという等式 $2$ つ、選んだ単項式の積の $x, y$ の次数が $X+N,Y+N$ に等しいという等式 $2$ つを満たすものを列挙すればよい。変数 $4$ つに対して等式が $4$ つあるので $O(1)$ で求まる。

任意の座標 $(x,y,z)$ から $(x \pm 1, y, z), (x, y \pm 1, z), (x, y, z \pm 1)$ に移動できる。$(0,0,0)$ から $(X,Y,Z)$ に $N$ 回の移動で到達する方法は何通りあるか。（出典:ABC240G）

求める値は
\begin{align}
&[x^Xy^Yz^Z](x+x^{-1}+y+y^{-1}+z+z^{-1})^N \\
=& [x^{X+N}y^{Y+N}z^Z]((1+xy)(x+y)+xyz+xyz^{-1})^{N}
\end{align}として表される。例１に比べて、$xyz,xyz^{-1}$ という単項式が加わり、自由度が $2$ つ増えた一方で、求める単項式について $z$ の次数が $Z$ に等しいという条件が加わった。従って、変数 $6$ つに対して $5$ の等式があるので、$O(N)$ で求まる。

なぜ因数分解で計算量改善するのか

求めたい値が $n$ 変数 $x_1,x_2,\ldots,x_n$ で表される多項式 $f$ の $N$ 乗の $\prod x_i^{e_i}$ の係数とする。
$f$ が $m$ 個の単項式からなるとする。それぞれ $f^N$ で $r_1,r_2,\ldots,r_m$ 回掛けたものが $\prod x_i^{e_i}$ に寄与するための条件は

$x_i$ の次数が $e_i$ である。
$\sum r_i = \sum e_i$ である。

が成り立つことである。$m$ 変数に対して $n+1$ 個の等式が課せられるので、条件を満たす $r$ の列挙には $O(N^{\max(m-n-1,0)})$ 掛かる。ただし、項数が $O(1)$ であると仮定している。

因数分解することで項数が減る

項数が減れば、自由度が減るので計算量は減少します。ただ、$1-x^n=(1-x)(1+x+\ldots+x^{n-1})$ のように、因数分解することで項数が増えることもあります。

因数分解することで、等式が増える。

多項式 $g$ について、$k$ 個の因数に分解できるとすると、
$$g^i = g_1^i g_2^i \ldots g_k^i$$ より、$g$ から選ぶ単項式の個数は $i$ 個であるという一つの条件が、$g_i$ から選ぶ単項式の個数は $i$ 個であるという $k$ 個の条件に分裂する。$x+y+x^2y+xy^2=(x+y)(1+xy)$ のように単項式の個数が変わらなくても課される等式が増えるので、計算量は減少する。

条件は独立か？

かならいさんに指摘されたことだが、制約が独立か確認しないといけないので、数を数えるだけで直ちに分かるというわけではなく、概算である。次の問題を考えてみる。

任意の座標 $(x,y,z)$ から $(x + 1, y, z), (x, y + 1, z), (x, y, z + 1)$ のいずれかに移動したあと、その座標を $(x’,y’,z’)$ として、$(x’-1, y, z), (x, y’-1, z), (x, y, z’-1)$ のいずれかに移動できる。この二つはセットで行わなければならない。$(0,0,0)$ から $(X,Y,Z)$ に $2N$ 回の移動で到達する方法は何通りあるか。

求める値は $[x^Xy^Yz^Z](x+y+z)^N(x^{-1}+y^{-1}+z^{-1})^N$ と表されて、一見、6変数に対して、変数の次数制約が3つ、単項式の次数制約が2つあるので1乗になりそうだが、実際は条件が従属なので、4条件しか残らず2乗になる。