はじめに
両側に境界がある一次元ウォークの数え上げについて考える。以下の設定それぞれについて考える。
- 始点と終点がそれぞれ一点 or 多点。
- $t$ 歩以下の歩数それぞれについて数え上げる or $t$ 歩のウォークだけを数え上げる。
- 足踏みなし or 足踏みあり。
準備
区間の長さは $n$ とする。つまり座標 $1,\,2,\dotsc, n$ の上をウォークする。1ステップで左右のどちらかに一歩動く。足踏みありの設定ではその場に留まることも許す。$a, b\in\{1,\dotsc,n\}$ を始点、終点として $a$ から $b$ へのウォークの個数を数える。多点の設定では始点の集合 $A$ と終点の集合 $B$ の間のすべてのパスの個数を数える。
関連して、 $e_a\in F^n$ を $a$ だけ 1 それ以外は 0 のベクトルとし、 $B_n\in F^{n\times n}$ を対角の隣が1でそれ以外が 0 の行列とする。
1D walks
一点, t 歩以下, 足踏みありなし O(t log n)
一点、足踏みなしの数え上げ母関数は以下で与えられる。
\begin{align*}
f(x) &:= \sum_{k=0}^\infty e_b^T B_n^k e_a x^k\\
&= e_b^T(I-xB_n)^{-1}e_a\\
&= \frac{(-1)^{a+b}\det((I-xB_n)_{-a,-b})}{\det(I-xB_n)}
\end{align*}
ここで $(I-xB_n)_{-a, -b}$ は $I-xB_n$ の $a$行と $b$列を取り除いた行列である。
分母を
Q_n(x):=\det(I-xB_n)
と定義する。
このとき、 $I-xB_n$ は三重対角行列であることから、行列式が漸化式
\begin{align*}
Q_0(x) &= 1\\
Q_1(x) &= 1\\
%Q_2(x) &= 1 - x^2\\
Q_n(x) &= Q_{n-1}(x) - x^2 Q_{n-2}(x)\qquad n\ge 2
\end{align*}
を満たすことが分かる。
通常の漸化式を満たす数列の $n$ 項目の計算と同じアルゴリズムで $Q_n$ は計算できる。
例えば
Q_n(x) = [u^n]\, \frac{1}{1-u+x^2u^2}
と表し、右辺に対して「線形漸化的数列のN項目の計算」を適用することで計算ができる。
このとき、$x$ の次数は1ステップで倍になり、最終的な次数は $O(n)$ なので、計算量は
\mathsf{M}(cn) + \mathsf{M}(cn/2) + \dotsb = O(\mathsf{M}(n))
である。また、$O(n)$ で $Q_n$ を計算する方法を おまけ: Qn, Rn の計算 O(n) で説明する。
あとは、分子にある小行列式 $\det((I-xB_n)_{-a,-b})$ が計算できればよい。
$a\le b$ と仮定して一般性を失わない。このとき行列 $I-xB_n$ の $a$ 行 $b$ 列を削除した行列の行列式を考えると、余因子展開するときに $a$ 行目から $b-1$ 行目は左下の非零成分を選ばないと0になることが分かる。この考察より
(-1)^{a+b}\det((I-xB_n)_{-a,-b}) = x^{b-a} Q_{a-1}(x) Q_{n-b}(x)
であることが分かる。
よって
f(x) = \frac{x^{b-a}Q_{a-1}(x)Q_{n-b}(x)}{Q_n(x)}
である。これを $t$次まで計算する計算量は $O((t/n)\mathsf{M}(n))$ である。
足踏みありの場合も同様に
R_n(x):=\det(I-x(I+B_n))
とすると、
\begin{align*}
R_0(x) &= 1\\
R_1(x) &= 1-x\\
R_n(x) &= (1-x)R_{n-1}(x) - x^2 R_{n-2}(x)\qquad n\ge 2
\end{align*}
を満たすことが分かり、上記と同様のアルゴリズムが構成できる。
プログラム例
F = GF(998244353)
R.<x> = F[]
# R_n を計算する
def charpoly(n):
S.<t> = R[]
Q = 1 - (1-x) * t + x^2 * t^2
P = S(1)
while(n != 0):
nQ = Q(-t)
P = S((P * nQ).list()[n%2::2])
Q = S((Q * nQ).list()[::2])
n //= 2
return P[0]
# 幅 n の足踏みあり 1d walk で始点 a 終点 b のものの個数の母関数を t 次まで計算する
def count1d(n, t, a, b):
Q = charpoly(n)
if a > b: a, b = b, a
P = x^(b-a) * charpoly(a-1) * charpoly(n-b)
return P.multiplication_trunc(Q.inverse_series_trunc(t+1), t+1)
多点, t 歩以下, 足踏みありなし ？
知らない。鏡像法 + 分割統治FFT ？
のDの解説参照。
一点 or 多点, t 歩以下, 足踏みあり (足踏みなしの計算量) + O(M(t))
一般的に足踏みなしの母関数から足踏みありの母関数に $O(\mathsf{M}(t))$ で変換する方法がある。指数型母関数の方が考えやすい。
\begin{align*}
\widetilde{g}(x)&=\sum_{k=0}^\infty\frac1{k!} e_B^T(I_n+B_n)^k e_A x^k\\
&= \sum_{k=0}^\infty\frac1{k!}\sum_{\ell=0}^k\binom{k}{\ell} e_B^T B_n^\ell e_A x^k\\
&= \sum_{k=0}^\infty\frac1{k!}\sum_{\ell=0}^k\binom{k}{\ell} f_\ell x^k\\
&= \sum_{k=0}^\infty\sum_{\ell=0}^k\frac1{(k-\ell)!}x^{k-\ell}\frac{f_\ell}{\ell!} x^\ell\\
&= \mathrm{e}^x\widetilde{f}(x)
\end{align*}
つまり
- 足踏みなしの指数型母関数 $\widetilde{f}$ を計算する
- $\widetilde{g}(x)=e^x\widetilde{f}(x)$ を計算する (計算量 $\mathsf{M}(t)$)
で足踏みありの指数型母関数 $\widetilde{g}$ が計算できる。
もちろん逆に $\widetilde{g}(x)$ に $\mathrm{e}^{-x}$ を掛けることで $\widetilde{f}(x)$ を計算することもできる。
多点, t 歩, 足踏みありなし O(M(n) log t)
鏡像法。
$$
(x + x^{-1})^t\sum_{a\in A}(x^a-x^{-a})\mod x^{2n+2}-1
$$
の $x^b$ の係数を $b\in B$ について足せばよい。 $(x+x^{-1})^t$ は繰り返し二乗法で計算する。一回のステップでは多項式の積を計算した後に自力で巡回させればよい。足踏みありの場合は $(x+x^{-1})$ の代わりに $(x+1+x^{-1})$。
一点, t 歩, 足踏みありなし O(M(n) log t)
多点と同じオーダーだが別の方法もある。定数倍がよいかどうかは不明。
[x^t]\,f(x) = [x^t]\,\frac{x^{b-a}Q_{a-1}(x)Q_{n-b}(x)}{Q_n(x)}
の右辺を「線形漸化的数列のN項目の計算」で計算すれば $O(\mathsf{M}(n)\log t)$ 時間である。
おまけ: Qn, Rn の計算 O(n)
Alin Bostan, Vincent Neiger, and Sergey Yurkevich. "Beating binary powering for polynomial matrices," In Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (ISSAC '23). Association for Computing Machinery, New York, NY, USA, 70–79, 2023. https://doi.org/10.1145/3597066.3597118
に書いてあることだが、短い漸化式を持つ多項式列に含まれる多項式は低階数の微分方程式を満たす。よって $Q_n,\,R_n$ の係数は短い漸化式を持つ。その漸化式にしたがって係数を計算すれば $O(n)$ で $Q_n,\,R_n$ が計算できる。
$Q_n(x) = \sum_{k=0}^n q_{n,k}\, x^k$とおくと、
\begin{align*}
q_{n,0} &= 1\\
q_{n,1} &= 0\\
q_{n,k} &= −\frac{4(n-k+1)(n-k+2)}{k(2n-k+2)} q_{n,k-2}\qquad k\ge 2
\end{align*}
を満たす。というか
\begin{align*}
q_{n,2k} &= (-1)^k \binom{n-k}{k}\\
q_{n,2k+1} &= 0
\end{align*}
である。
また、$R_n(x) = \sum_{k=0}^n r_{n,k}\, x^k$とおくと、
\begin{align*}
r_{n,0} &= 1\\
r_{n,1} &= -n\\
r_{n, k} &= -\frac{n-k+1}{k(2n-k+2)}\bigl((2n-2k+3)r_{n,k-1} + 3(n-k+2)r_{n,k-2}\bigr)\qquad k\ge 2
\end{align*}
である。自己責任で。