問題概要

解法

とりあえず置いてはいけない箇所の制約を無視する。

$\displaystyle{ f(x) = \sum_{k=1}^ \infty k^ 2 x^ k }$

とおけば、置いてはいけない場所がなかった状態での求めるべき値は $\displaystyle{\frac{f}{1-f}}$ の $\displaystyle{x^ n}$ の係数。

$\displaystyle{n \geq 1}$ であるからまあ $\displaystyle{\frac{1}{1-f}}$ としてもよい。さて、具体的にこの関数の $\displaystyle{n}$ 次の係数を $\displaystyle{a_n}$ とすると、

$\displaystyle{1-f}$ のinverseであるから、漸化式

$\displaystyle{ a_n = \sum_{k=0}^ {n-1} a_k (n-k)^ 2 }$

となる。まあdpから考えれば自明に出てくる式で、いちいちFPSを経由しなくても良い。

高　　校　　数　　学

さて、上記漸化式が $\displaystyle{n}$ について成り立っている時、命題 $\displaystyle{C(n)}$ が成立していると呼称することにする。

$\displaystyle{C(n)}$ と $\displaystyle{C(n+1)}$ が成立しているならば、

$\displaystyle{ a_n = \sum_{k=0}^ {n-1} a_k (n-k)^ 2 }$

$\displaystyle{ a_{n+1} = \sum_{k=0}^ {n} a_k (n+1-k)^ 2 }$

である。 2等式を差し引きしてやると、

$\displaystyle{ a_{n+1} - a_n = a_n + \sum_{k=0}^ {n-1} a_k (2n-2k+1) }$

$C(n+1), C(n+2)$ を仮定すれば

$\displaystyle{ a_{n+2} - a_{n+1} = a_{n+1} + \sum_{k=0}^ {n} a_k (2n-2k+3) }$

この2等式を差し引きしてやると、

$\displaystyle{ \begin{aligned} a_{n+2} - 2 a_{n+1} + a_n &= a_{n+1} - a_n + 3 a_n + 2 \sum_{k=0}^ {n-1} a_k \\ \iff a_{n+2} - 3 a_{n+1} - a_n &= 2 \sum_{k=0}^ {n-1} a_k \end{aligned} }$

最終的に、 $C(n), C(n+1), C(n+2), C(n+3)$ を仮定すれば

$\displaystyle{ a_{n+2} - 3 a_{n+1} - a_n = 2 \sum_{k=0}^ {n-1} a_k }$

$\displaystyle{ a_{n+3} - 3 a_{n+2} - a_{n+1} = 2 \sum_{k=0}^ {n} a_k }$

より

$\displaystyle{ a_{n+3} - 4 a_{n+2} +2 a_{n+1} - a_n = 0 }$

が出る。今回は $f$ が綺麗な形をしていたため、このように高校数学をやって出せば終わるが、そうでない場合はberlekamp-masseyの根幹的なアイデアであるところの、母関数と漸化式の関係を考えて分母を出す必要がある（というより、一旦分かりやすい関数の積に分離+それぞれで高校数学+心温まる手筆算でそれらを合成みたいな感じになる）。

さて、 $C(n)$ を明示的に用いて導出を行ったのは、最終的な漸化式 $a _ {n+3} - 4 a _ {n+2} +2 a _ {n+1} - a _ n = 0$ が成立するためには、 $a _ n, a _ {n+1}, a _ {n+2}, a _ {n+3}$ の連続する4項について、元の漸化式

$\displaystyle{ a_n = \sum_{k=0}^ {n-1} a_k (n-k)^ 2 }$

が成立する必要があるということを明確にするためである。すなわち、この問題の条件として存在している、「 $X_k$ は通ってはいけない」によって強制的に $a _ {X _ k} = 0$ となっている付近では、この4項間漸化式は成立しないことを意味する。逆に、成立するためには直近の4項さえ元の漸化式を満たしていれば良い。すなわち、それより以前の項がいくつ強制的に定数に書き換わっていても、この漸化式を用いて計算を行って良い。したがって、 $X_k$ 付近以外は行列累乗によって計算できることが分かり、後は $X_k$ 付近を項ごとに $O(1)$ 程度で計算できれば良い。

さて、 $X_k$ 付近については気合で求める。というのも、以下の等式自体は、 $C(n), C(n+1)$ を仮定するだけで言えるのであった:

$\displaystyle{ a_{n+1} = 2 a_n + \sum_{k=0}^ {n-1} a_k (2n-2k+1) = 2 a_n + (2n+1) \sum_{k=0}^ {n-1} a_k - 2 \sum_{k=0}^ {n-1} k a_k }$

すなわち、 $C(n)$ さえ成立していれば、 $C(n+1)$ を満たす $a _ {n+1}$ は、 $a _ k$ および $k a _ k$ の総和さえ保持しているだけで、 $O(1)$ で計算できる。問題は、 $C(n)$ を満たしていない時である。この時 $a _ n = 0$ となるわけであるが、

「仮に $C(n)$ が成立していたとすると、 $a _ n$ はいくつであったか」を求めることは上記の行列累乗ないし愚直な計算を用いて可能である。

これを $a' _ n$ とおく。
$a' _ n$ を用いれば、「仮に $C(n)$ が成立していた時、 $a _ {n+1}$ がいくつであったか」も求まる。

これを $a' _ {n+1}$ とおく。すると、元の漸化式を考えた時、 $a' _ {n+1} - a' _ n = a _ {n+1}$ が成立する。よって、このケースにおいても $O(1)$ で計算できる。

さて、残った問題は $a _ k$ および $k a _ k$ の総和を保持する必要が生じたこと。これによって行列累乗中でこれらの値についても計算する必要が出てくる。これは †気合†でやればよい

全部できたので、オッケー

これ、解説の言い換えでやると多分こんな爆発ad-hocクソ面倒行列累乗にはならない気がしていて、言い換えって大事なんだねーと思ってます。今

Open Problem

結局FPSで定式化しようとしたがうまくいかなかったので方針修正を行った結果かなり遠回しな解法になった。実はFPSでもある程度までは綺麗な定式化が出来る。今回は $N$ が $10^ 9$ なので最終的にはどうにもならないにしても、 $10^ 5$ オーダーでFPSの操作だけで殴れたら嬉しいに決まっている。あるいは、 $10^ 9$ オーダーであっても、綺麗にFPSの操作で問題が記述できていれば、高校数学など手計算でちゃんと答えが求まる可能性もある。

困っているのは定式化すると最終的に出てくる方程式が解けないという点。とりあえずこれについて書いておく。

まず問題を以下の様に一般化する:

問題石 $0$ , ... , 石 $N$ が一直線上に並んでおり、カエルが石 $0$ にいる。カエルは長さ $k$ のジャンプをコスト $C _ k$ で出来る。石 $0$ から石 $N$ へいく経路を考える。経路のコストを、行ったジャンプのコストの総積とする。全ての可能な経路のコストの総和を求めたい。ただし、石 $B _ 1$ , ..., $B _ M$ には入ってはならないこととする。

まず、

$\displaystyle{ f(x) = \sum_{k=1}^ \infty C_k x^ k }$

とすれば、元の問題と同様に、 $B _ i$ の制約を無視すれば $\displaystyle{\frac{f}{1-f}}$ が可能な移動を表すFPS。ここで、FPSの作用素（FPSからFPSの写像） $D(f)$ を、「 $f$ 中の $B _ i$ 次の項のみ取り出す操作」として定義する。作用素 $D$ は明らかに線形性・冪等性などを持つ。

今、 $\displaystyle{\frac{1}{1-f}}$ 中に含まれる、「本来禁止されていたはずの経路のコスト」を引きたい。

このために、FPS $G _ 1, G _ 2, ...$ を、

$\begin{aligned} G _ 1 &= D(f) \\ G _ 2 &= D(f^ 2) - D(f G _ 1) \\ G _ 3 &= D(f^ 3) - D(f G _ 2) - D(f^ 2 G _ 1) \\ ... \end{aligned}$

すなわち、

$\displaystyle{ G _ k = D(f^ k) - \sum_{i=1}^{k-1} D(f ^{k-i} G _ i) }$

として定める。

$G _ k$ は何を表してるかというと、

「 $k$ 回のジャンプであって、ぴったり $k$ 回目で禁止された場所に移動してしまったもののコストの総和」

である。これが分かると、 $\frac{1}{1-f} G _ k$ は「 $k$ 回目のジャンプで初めて禁止された場所にきてしまった経路全体」を表すことになるので、これの総和を取って、

$\displaystyle{ \frac{1}{1-f} \sum_{k=1}^\infty G _ k }$

が求めたい引くコスト全体。

定義式に基づいて、 $\sum_{k=1}^\infty G _ k$ の具体的な値について考えてみると、

$\displaystyle{ \sum_{k=1}^\infty G _ k = \sum_{k=1}^\infty D(f ^k) - \sum_{i=1}^\infty \sum_{k=1}^\infty D(f ^k G _ i) }$

となっている。 $D$ の線形性に気をつければ、これは、

$\displaystyle{ \sum_{k=1}^\infty G _ k = D(\frac{f}{1-f}) - D(\frac{f}{1-f} \sum_{i=1}^\infty G _ i) }$

となる。 $G = \sum_{k=1}^\infty G _ k$ とおくと、

$\begin{aligned} G = D(\frac{f}{1-f}) - D(\frac{f}{1-f} G) \\ \end{aligned}$

という方程式を満たすような $G$ が求めたいという問題になる。 $G = D(G)$ に気をつけると、

$\begin{aligned} D(G) = D(\frac{f}{1-f}) - D(\frac{f}{1-f} G) \\ \iff D(\frac{G}{1-f}) = D(\frac{f}{1-f}) \end{aligned}$

となり、 $G = D(G)$ を満たす（すなわち、 $B _ i$ 次の項しか持たないような多項式の）中で、これが成立するような $G$ を求めたくなる。

これは、 $G = \sum_{i} a _ i x ^ {B _ i}$ とおくと、

$\displaystyle{ \sum_{i} a _ i D(\frac{x ^ {B_i}}{1-f}) = D(\frac{f}{1-f}) }$

なる $\{a _ i\}$ を求めるのと同値であり、 $D(\frac{x ^ {B_i}}{1-f})$ をそれぞれ求めて、係数をベクトルだと思うことにするとある種の連立方程式であるということは分かる。が、 $O(n^ 3)$ 以下の解法があるのか、すなわち、 $D(\frac{x ^ {B_i}}{1-f})$ を列ベクトルとしてもつような行列の逆行列が高速に求められるのかが謎.....