概要
第１回：数え上げとの対応付け → ■
前回は、いろいろな数え上げの問題が、多項式（形式的べき級数）の問題に変換されることを確認しました。しかしこれだけでは、通常の dp の考え方をそのまま翻訳しただけです。まぁデータの持ち方を多項式にしただけですからね。
多項式に言い換えられる時点で、 dp の遷移の立式はできているわけです。一方で、時にはそのままの立式に基づくと計算量が大きすぎて、計算量の削減に迫られるときもあるでしょう。何らかの式変形の形により高速計算がしやすい形にもっていく必要があります。 このような事例を見ていきましょう。
前提となる代数
とりあえず、この記事では次のような文字式の計算を利用します。
二項定理
\[(x+y)^n = \sum_{0\leq i\leq n}\binom{n}{i}x^iy^{n-i}\] が成り立つ。
$\binom{n}{i}$ は二項係数で、${}_n\mathrm{C}_i$ の表記をする場合もあります。
なお、$i<0$ や $i>n$ に対して $\binom{n}{i}=0$ なので、和のとる範囲は適当でよくて、例えば $\sum_{i=0}^{\infty}$ と書いたりしてもよいです。
等比数列の和
$r\neq 1$ に対して、\[\sum_{i=0}^{n-1}r^i = \frac{1-r^n}{1-r}\]が成り立つ。
形式的べき級数の和・差・積
$F=\sum_{n=0}^{\infty}f_nx^n$ のような式を、形式的べき級数といいます。多項式もある種の形式的べき級数です。
$G = \sum_{n=0}^{\infty} g_nx^n$ も形式的べき級数とするとき、これらの和・差・積が次の要領で定義されます：\[[x^n](F\pm G) = f_n \pm g_n,\qquad [x^n](FG) = \sum_{i+j=n}f_ig_j.\] 個別の係数の定義には無限和が現れないため、極限操作などを必要とせず純代数的に定義が可能です。
重要な性質として、$F\pm G $・$FG$ の $n$ 次未満の部分は $F,G$ の $n$ 次未満だけから決まります。$n$ 次未満だけに注目すると、形式的べき級数の演算規則は多項式の演算（より正確には多項式 $\pmod{x^n}$ の演算） と同一です。
このことから、形式的べき級数の和・差・積は、交換法則・結合法則・分配法則など、演算に関する自然な要請を十分に満たすことも分かります。
（※ 専門用語で、環をなすという）
（※ 多項式環から形式的べき級数環を得る操作は、「環のイデアルによる完備化」という操作の特殊な場合。重要な類似物に、$p$ 進整数環など。
より詳細が気になった場合には、次の記事も適宜参照してください。とはいえある程度雰囲気が分かったら、厳密な定義などは気にせず本記事を読み進めて頂ければよいと思います。
形式的べき級数環の位相
「位相」というのは、「極限」を定義するための構造です。言葉を持ち出しましたが、位相空間などの知識は必要ありません。また厳密なことが分かっていなくても、雑に扱ってしまって正しい結論になることが多いので、難しそうならば読み飛ばしても大丈夫です。
形式的べき級数 $F$ は、最低次の項が高いほど、$0$ に近いと考えて扱います。このことを利用して、形式的べき級数の列の極限を定義することができます：
【定義】
形式的べき級数列 $F_1,F_2,F_3\cdots$ が $F$ に収束するとは、任意の $k$ に対してある $N$ が存在して、$n\geq N$ ならば $F_n$ と $F$ の $k$ 次未満部分が一致することを指す。
数列の極限が定義されたので、無限級数の極限も部分和の極限として定義できます。
形式的べき級数の逆元
形式的べき級数 $F,G$ に対して $FG = 1$ が成り立つとき、$F$ を $G$ の（あるいは $G$ を $F$ の）逆元といい、$F = \dfrac{1}{G}$ などと書きます。$F\cdot \dfrac{1}{G}$ を $\dfrac{F}{G}$ と書きます。
いわゆる分数と同じ表記をしますが、実際に分数と同様の計算ルール（$\dfrac{F_1}{G_1}\pm\dfrac{F_2}{G_2}=\dfrac{F_1G_2\pm F_2G_1}{G_1G_2}$ など）を満たすことが確認できます（分数の計算ルールは、結合法則・分配法則などから導かれます）。逆元としては、次が最頻出です。
\[\frac{1}{1-x} = 1 + x + x^2 + x^3 + x^4 + \cdots = \sum_{n=0}^{\infty}x^n.\]
実際、$(1-x)(1+x+x^2+x^3+\cdots)$ を計算してみようとすると、係数が定数項を除き $0$ になることが確認できます。 同様に、$F$ が定数項を持たない形式的べき級数であるとき
\[\frac{1}{1-F} = 1 + F + F^2 + F^3 + F^4 + \cdots = \sum_{n=0}^{\infty}F^n.\]
が成り立つことが分かります。
右辺はちゃんとやると、上述の「形式的べき級数環の位相」で述べた極限概念です。部分和が等比数列の和から $\dfrac{1-F^N}{1-F}$ の形、左辺との差は $\dfrac{F^N}{1-F}$ となりますが、$F$ に定数項がなければこの式に $N$ 次未満の項は存在せず、正当性が保証されます。
無限和の式変形による簡略化
【問題】
$N$ を正の整数の和として表す方法を数え上げよ。ただし、和の順序の違いは区別する。
$N=4$ なら、$4, 1+3, 3+1, 2+2, 1+1+2, 1+2+1, 2+1+1, 1+1+1+1$ の $8$ 通りがあります。 この問題は、和をとる個数 $n$ ごとに計算すると、次のように多項式計算に帰着できました。
$F=x+x^2+x^3+x^4+\cdots$ とするとき、$[x^N]\sum_{n=0}^{\infty}F^n$ が答である。
実はこの時点で、一番短い解法（組合せ解釈で一瞬）と比べるとかなり遠回りをしてしまっています。無限和になっていますし。
それでも「文字式を式変形で簡単にしていく」という視点で自然に解けることを確認しましょう。
まず、$F=x\cdot \dfrac{1}{1-x}=\dfrac{x}{1-x}$ です。調べたいものは $G = \sum_{n=0}^{\infty}F^n$ ですが、これは $G=\dfrac{1}{1-F}$ と表せます。$F = \dfrac{x}{1-x}$ を代入して整理すると、\[ G = \frac{1-x}{1-2x}\] であることが分かります。
\[G = (1-x)\cdot \frac{1}{1-2x}=(1-x)(1+2x+4x^2+8x^3+\cdots)\] などとして計算すると、$N$ 次の係数は、$N=0$ のとき $1$、$N\geqq 1$ のとき $2^N-2^{N-1}=2^{N-1}$ であることが分かります。
あるいは、次のような変形をしても同じ結論が得られます： \[G = \frac12 + \frac12\cdot\frac{1}{1-2x} = \frac12 + \frac12(1+2x+4x^2+8x^3+\cdots).\]
コメント
とにかく文字式の問題に翻訳できてさえいれば、あとはその文字式のなるべく自然な表示を探ってあげることで、数え上げ対象の簡単な表示や計算方法が見えてきます。文字式の式変形の力量を、直接的に数え上げに活かすことができます。
なお、恐らく最も易しい方法は、組合せ的な解釈（対応付け）を利用するもの。
$4＝1＋2＋1$ → 〇｜〇〇｜〇 （$1$ 個・$2$ 個・$1$ 個の〇の間に仕切りを入れる）
とすると、$4$ の分割が、「$3$ ヶ所に対して仕切りを入れる・入れないの2択を行うこと」と対応して、$2^3$ 通り。
因数分解の利用
文字式が因数分解されると、それに従って計算手順が簡略化される場合があります。例えば、次を見てみましょう。
【問題】■
座標平面上を、原点から出発してランダムウォークする。$T$ 秒後に $(a,b)$ に到達する移動経路数を求めよ。
※ 二項係数の事前計算のもと、1件あたり $O(1)$ 時間で計算せよ
この問題は、多項式によって次の形に言い換えることができるのでした：
$F = (x + x^{-1} + y + y^{-1})$ とするとき、$[x^{a}y^{b}] F^{T}$ を求めよ。
$F$ は、次のように因数分解できます：\[ F = (xy)^{-1}(x^2y + xy^2 + x + y) = (xy)^{-1}(xy+1)(x+y).\] $F^T$ を二項定理で展開してみましょう。
\[\begin{align*} (xy)^{-T}(xy+1)^{T}(x+y)^{T} &= (xy)^{-T} \sum_{i,j}\binom{T}{i}\binom{T}{j}(xy)^{i}1^{T-i}x^{j}y^{T-j}\\ &= \sum_{i,j} \binom{T}{i}\binom{T}{j} x^{i+j-T}y^{i-j}.\end{align*}\]
したがって、$[x^{a}y^{b}] F^{T}$ を計算するに際しては、$I = \{(i,j)\mid i+j-T=a, i-j=b\}$ として $\sum_{(i,j)\in I}\binom{T}{i}\binom{T}{j}$ を計算すればよいです。$I$ は高々 1 元集合になって、計算結果が得られます。
コメント
この問題は $1$ 次元なら簡単ですので、2 次元の場合も移動回数を $x$・$y$ 方向に割り振れば、経路数は適当な二項係数の積で表されます。よって、二項係数のシグマ計算による立式がすぐに出来て、これをうまく処理しても解くことができます。
本問題は、DEGwerさんの、数え上げPDF（■）でも取り上げられています（14.3節）。$45$ 度回転する、要するに $(x,y)$ の代わりに $(x+y,x-y)$ を考えるというものです。
この考え方と、上記の因数分解による考え方は対応しています。
$A = x^{1/2}y^{1/2}$, $B = x^{1/2}y^{-1/2}$ とすると、$f = (A+A^{-1})(B+B^{-1})$ と書くことができて、1 回の遷移が「$A$ または $A^{-1}$ を選ぶ」「$B$ または $B^{-1}$ を選ぶ」を独立に行うことだと思えます。これが、$45$ 度回転盤面で左右・上下の移動を独立に選ぶことと対応します。
文字式に対する自然な（中高数学の代数で慣れている）操作から、数え上げに対するアドホックな言い換えが自然に導かれていることに注目してください。（文字式の操作・数え上げの言い換え、それぞれがどのくらい自然に思えるのかは人それぞれなんですが）
類題
問題と、対応する私の解説記事を 1 つ貼っておきます。
問題 → ■、解説 → ■
二項係数の多重和をいじると思っても、45 度回転のような言い換えを探すと思っても、かなり上位の問題になると思いますが、多項式を因数分解するという視点に立てば類題の範疇になっていると思います。
累積和による dp 遷移の導出
【問題】■
$a_1,\ldots, a_N$ が与えられる。自然数 $0\leqq x_i\leqq a_i$ を選んで、$x_1+\cdots + x_N = K$ となるようにする方法の総数を求めよ。
※ $N\leqq 100$, $a_i\leqq K\leqq 10^5$.
多項式の問題に置き換えると、次のようになります。
$F_{i} = 1 + x + x^2 + \cdots + x^{a_i}$ とする。$[x^K] F_1F_2\cdots F_N$ を計算せよ。
一般に、$d$ 次多項式の積は愚直計算で $\Theta(d^2)$ の計算量が必要になって、$K$ 次式の積を $N$ 回行うのは本問の制約では難しいです。
$F_i$ に対して何らかの構造を見出して、計算量を落としましょう。因数分解のときと同様にして、多項式に対するよりいい感じの表示を探していきます。
等比数列の和から、$F_i = \dfrac{1-x^{a_{i}+1}}{1-x}$ と式変形できます。割り算ですが、疎な（係数がほとんど $0$ であるような）多項式 $2$ つで表せており、より上手く $F_i$ を扱えそうです。さらに、\[F_i = \frac{1}{1-x}\cdot (1-x^{a_i+1})\] と表してみましょう。「$F_i$ を因数分解した」と考えても、まぁ良いと思います。（多項式の範囲だけで物事を見ていると $\dfrac{1}{1-x}$ という式が扱えなくて、ある意味では考察の範囲を形式的べき級数に広げて考える利点が現れています。）
結局のところ、ある多項式 $P$ に $F_{i}$ をかける操作は、次のように分解することができます。
- 操作１：$\dfrac{1}{1-x}$ をかける
- 操作２：$(1-x^{a_i+1})$ をかける
操作１はどのように計算できるでしょうか？
一般に、$P = \sum_{n=0}^{\infty}p_nx^n$, $\dfrac{P}{1-x} = Q = \sum_{n=0}^{\infty}q_nx^n$ としてみましょう。割り算よりも掛け算の方が理解しやすいので、これらの関係を $(1-x)Q = P$ と表します。
両辺の $[x^n]$ 部分を比べると $p_n=q_n$ であることと、$n\geqq 1$ に対して $q_n-q_{n-1}=p_n$ が成り立つことが分かります。したがって $q_n$ は漸化式 $q_n=q_{n-1}+p_n$ と初項 $q_0=p_0$ で計算していくことができて、係数 $1$ つあたり $\Theta(1)$、$d$ 次以下の部分を $\Theta(d)$ で計算できます。
※ 一般に、疎な多項式による割り算は同じように高速に計算できます。
※ 結局、$\{q_n\}$ は $\{p_n\}$ の累積和です。 $\frac{1}{1-x}=1+x+x^2+\cdots$ に基づく説明も可能で、その方が分かりやすいかもしれませんが、「疎な式への分解」を発見すれば自然に計算量が落ちるという思考法を強調するため上記の説明をとりました。
操作２はどうでしょう？これは掛け算の定義通りに計算するだけで，同様の計算量で計算できます。係数の列を $(a_i+1)$ 個ずらして引くだけです（一般に、疎な多項式との掛け算は高速に計算できます）。
両方の操作をまとめると、結局 $F_i$ による dp 遷移は、
- 数列を累積和に置き換える
- $(a_i+1)$ 個ずらしたところとの差分をとって、新たな数列を得る
という形で計算できることが分かりました。
なお、形式的べき級数の積は交換法則を満たすため、この 2 つの手順を逆順に行っても同じ計算結果が得られることが分かります。$N$ 個の積 $f_1\cdots f_N$ を計算するにあたって、$\prod_i(1-x^{a_i})$ を計算したあとで $N$ 回累積和をとるような計算手順も可能であることが分かります。お好みの順序で実装しましょう。
- 実装例(1)：https://atcoder.jp/contests/dp/submissions/45905298
- 実装例(2)：https://atcoder.jp/contests/dp/submissions/45905363
なおより高度なアルゴリズムを学べば、$\exp, \log$ 等を使って $N=10^5$ などの制約で解くこともできます。
戻すDPの導出
【問題】■
$a_1,\ldots, a_N$ が与えられる。自然数 $0\leqq x_i\leqq a_i$ を選んで、$x_1+\cdots + x_N = K$ となるようにする方法の総数を求めよ。
いや、これは少し簡単過ぎるので、ちょっとした注文も追加する…
「$x_k = c_k$ のもとで数え上げよ」というクエリ $Q$ 個に答えよ。
※ $N\leqq 2000, 0\leqq a_i\leqq M\leqq 2000, Q\leqq 500000$
前問題の変形バージョン。クエリが $Q$ 個ありますが、たくさんありすぎるので結局すべての $(k, c_k)$ に対して計算することが想定されています。次の問題を解きましょう。
$F_{i} = 1 + x + x^2 + \cdots + x^{a_i}$ とおく。各 $i$ に対して、$\prod_{j\neq i}F_j$ の $M$ 次以下の部分を計算せよ。
全体集合から $1$ 元抜いたところで何か集計する場合には、左右からの累積を計算するのが典型テクニックです（例：■）。しかし、左右からの積をマージするところに $\Theta(M^2)$ かかるので、それを $N$ 回やるのは大変です（※ それでもFFTで高速化すればACが得られます）。もう少し良い構造を見つけたいところです。
他の方法として、
- $F = \prod_{j} F_j$ を計算する
- $\prod_{j\neq i}F_j = F / F_i$ として目的物を得る
という方法も、ごく自然に考えられます。$F_i$ による除法はどうなるでしょうか？
$F_i = \dfrac{1-x^{a_i+1}}{1-x}$ でした。よって \[ \frac{F}{F_i} = F\cdot (1-x)\cdot \frac{1}{1-x^{a_i+1}}\] と書くことができます。$F$ から $\frac{F}{F_i}$ を得る操作は、次の通りです：
- $(1-x)$ をかける
- $(1-x^{a_i+1})$ で割る
どちらも疎な多項式による乗算・除算なので、$\Theta(M)$ で計算できて目的が達成されます。より具体的な係数に対する操作としては、
- 階差数列をとる
- $d = a_i+1$ 項ごとの累積和をとる（$a_n \leftarrow a_n + a_{n-d}$ を小さい $n$ から繰り返す）
となります。
コメント
累積和による dp 更新・戻す dp といった個別の思えるテクニックが、文字式で見ると単純な掛け算・割り算で同時に説明されています。立式で混乱する要素も少ないでしょう。
交換法則・繰り返し二乗法の適用
【問題】■
‘ ? ? 2 ? ? 5′ のような文字列が与えられる。それぞれの「’?’」を 0 ～ 9 まで埋めて、$13$ の倍数を作る方法を数え上げよ。
※ 桁数：$N\leqq 10^5$.
まず、多項式乗算に帰着します。
- 1の位：$+5$ する。
- 10の位：$+0, +10, +20, +30, \ldots, +90$ から選ぶ。
- 100の位：$+0, +100, +200, +300, \ldots, +900$ から選ぶ。
- 1000の位：$+2000$ する。
既に埋まってる数値部分はそれっぽく遷移。それ以外は、$10^k$ の位のところに多項式 $F_k = \sum_{n=0}^{9}x^{10^kn}$ を当てます。
これらの積を計算すればよいですが、指数の $\pmod{13}$ での値だけが問題です。よって、$x^{13}=1$ というルールを追加した上で多項式の積を計算していくことになります（詳しい人向け：多項式環の剰余環 $K[X]/(X^{13}-1)$ における積）。
$x^5$ などをかけるのは係数の位置をずらすだけです。さらに、$F_n = F_{n+6}$ を利用すると、次が本質ということが分かります：
$F_0^{a_0}F_1^{a_1}\cdots F_5^{a_5}$ を（$x^{13} = 1$ のもとで）計算せよ。$\sum a_i = N \leqq 10^5$。
愚直計算で、多項式の積を $N$ 回程度計算することになります。（この方法でも解けて、コンテスト想定解と同等）。しかし、大きな $a$ に対して $F^a$ の計算する方法といえば、$\Theta(\log(a))$ の回数の乗算で計算できることはよく知られた通りかと思います。
結局、この問題の主要部は $N$ について $\Theta(\log N)$ 時間で計算できます（’?’ の位置を検出するところに $\Theta(N)$ 要るので結局全体では $\Theta(N)$ 解法）。
コメント
本問題で計算量が落ちることに言及していた人は少なかったような気がします。繰り返し二乗法の適用にあたり、多項式の積の
- 交換法則
- 結合法則
が本質的に使われています。が、多項式に対するこれらの性質は、新しいアルゴリズム知識として学ばずとも、空気のように使える方が多いのではないでしょうか？上の解説でも、交換法則や結合法則を利用した場所を明示していません。
dp の遷移の言葉で言うならば、
- 数列の畳み込みは結合・交換法則を満たす
- 遷移は線形なので行列で書けて、よって結合法則を満たす
などの形になると思いますが、多項式と違って高校数学までで馴染みが薄い人の方が多いと思います。また、この手の高速化は「行列累乗」というくくりで定跡化され語られているのをよく見かけますが、多項式で解釈できる場合にはそのようにしておいた方が、計算量も有利になります（$D$ 次多項式の乗除の愚直計算は $\Theta(D^2)$ で、$D$ 次正方行列の乗除の愚直計算は $\Theta(D^3)$ です）。
まとめ
例をたくさん挙げようとすると、収集がつかなくなってきそうでしたので、この辺でいったん終わります。
今回の内容についてより積極的な主張をすると、
- 問題が多項式・形式的べき級数の形で自然に表現できている
- 何らかの構造（組合せ的解釈など）により、dp がうまく計算できる
ときには、その構造を代数的な変形として導出できるだろうということになります。
今回取り上げたのは、どの問題も、多項式という考え方がなくとも解けるものばかりです。またひとつひとつの問題自体は、組合せ的解釈などによる方が簡単に、あるいは自然に立式できていると感じる方も多いと思います。ただ、一見すると全く異なる数え上げテクニックが、文字式を簡単にするという共通の考え方から同じように導かれているところは注目に値すると思います。