AtCoder Beginner Contest 213 H - Stroll

前置き

公式解説とは異なる $O(N ^ 3 T\log T)$ 解法を説明します。

問題リンク

atcoder.jp

解法

まず、形式的冪級数 $f _ i$ を次のように定めます。

$\displaystyle f_i=\sum_{d=0}^\infty \text{($d$ キロメートル歩いて頂点 $i$ にいる場合の数)}\cdot x^d$

また、 $1\leq i,j\leq N$ に対して形式的冪級数 $g _ { i , j }$ を次のように定めます。

$\displaystyle g_{i,j}=\sum_{d=0}^\infty \text{($j$ から $i$ への長さ $d$ キロメートルの道の本数)}\cdot x^d$

このとき、 $f$ と $g$ の間に次の関係式が成り立ちます。

$\displaystyle f_i=\sum_{j=1}^N f_j\ast g_{i,j}+ \begin{cases} 1 & \text{if $\;i=1$} \\ 0 & \text{otherwise} \end{cases}$

ここで、 $\ast$ は畳み込み演算です。この関係式を行列を用いて表せば、 $f$ に関する方程式が得られます。

$\displaystyle \begin{pmatrix} f_1 \\ f_2\\ \vdots \\ f_N\end{pmatrix}= \begin{pmatrix} g_{1,1} & g_{1,2} & \cdots & g_{1,N} \\ g_{2,1} & g_{2,2} & \cdots & g_{2,N} \\ \vdots & \vdots & \ddots & \vdots \\ g_{N,1} & g_{N,2} & \cdots & g_{N,N} \end{pmatrix} \begin{pmatrix} f_1 \\ f_2\\ \vdots \\ f_N\end{pmatrix} + \begin{pmatrix} 1 \\ 0\\ \vdots \\ 0\end{pmatrix}$

これを $f$ について解きます。

$\displaystyle \begin{pmatrix} f _ 1 \\ f _ 2\\ \vdots \\ f _ N \end{pmatrix}= \begin{pmatrix} 1 - g _ {1, 1} & g _ {1,2} & \cdots & - g _ {1,N} \\ - g _ {2,1} & 1 - g _ {2,2} & \cdots & - g _ {2,N} \\ \vdots & \vdots & \ddots & \vdots \\ - g _ {N,1} & - g _ {N,2} & \cdots & 1 - g _ {N,N} \end{pmatrix} ^ {-1} \begin{pmatrix} 1 \\ 0\\ \vdots \\ 0 \end{pmatrix}$

ここで、右辺に現れる逆行列が存在するかが問題となります。これは、制約から $[x ^ 0]g _ { i , j } = 0$ であり、対角成分にしか非零の定数項が存在しないことに注目するとその存在を示すことが出来ます*1。

以上より、 $T+1$ 次以上の項を切り捨てながら掃き出し法を行うことで、 $O(N ^ 3 T\log T)$ で逆行列 *2 が求まり、この問題を解くことが出来ました。

なお、逆行列のすべての成分を計算すると C++ で 4000 ms 程度かかってしまいますが、この問題では逆行列の $(1,1)$ 成分しか必要ないためかなりの計算を省略することができ、1000 ms を切ることが出来ます。

実装

逆行列のすべての成分を計算する実装例 (C++, 4132 ms)

逆行列の (1,1) 成分だけを計算する実装例 (C++, 914 ms)

*1:対角成分にしか非零の定数項が存在しないことから、行列式

$\displaystyle \sum _ { \sigma \in \mathfrak { S } _ N} \mathrm { sgn } ( \sigma ) \prod _ { i = 1 } ^ N (E-G)_{i,\sigma(i)}$

において $\displaystyle [x ^ 0] \prod _ { i = 1 } ^ N (E-G)_{i,\sigma(i)} \neq 0$ となり得る $\sigma$ は恒等置換 $\sigma = \mathrm{Id}$ のみであり、このとき $\displaystyle [x ^ 0] \prod _ { i = 1 } ^ N ( 1 - g _ { i , i } ) = 1$ です。従って、行列式が可逆なので正則であることが言えます。(可換環の元を係数に持つ形式的冪級数は可換環を成し、可換環上の行列が正則であるための必要十分条件は、その行列式が可逆元であること (らしいです、私は代数に明るくないので、誤りがあれば指摘頂けるとありがたいです) )