公式

H - Random Robots 解説 by penguinman


この問題を解く際には、LGV 公式というものが有用です。

この問題において用いられる LGV 公式の特殊形

DAG(有向無閉路グラフ)があり、そのうち $n$ 個の頂点 $a_1,a_2,\ldots,a_n$ が始点として、$n$ 個の頂点 $b_1,b_2,\ldots,b_n$ が終点としてマークされているとします。

このとき、すべての整数の組 $(i,j,k,l)\ (1 \leq i,j,k,l \leq n)$ について「$i \lt j$ かつ $k \lt l$ ならば $a_i$ から $b_l$ に向かうパスと $a_j$ から $b_k$ に向かうパスは必ず頂点を共有する」という条件が満たされるとき、以下の主張が成り立ちます。

  • パスの $n$ 個組であって、そのうち $i$ 番目のものの始点は $a_i$、終点は $b_i$ であり、かつどの $2$ つのパスも頂点を共有しないようなものの数は以下によって定められる $n \times n$ の行列 $X$ の行列式に等しい。
    • 任意の整数対 $(i,j)\ (1 \leq i,j \leq n)$ について、$X_{i,j}$ は $a_i$ から $b_j$ に向かうパスの個数に等しい

\(N\) 回の操作が終わったあと、ロボット \(1,2,\ldots,K\) がそれぞれ座標 \(y_1,y_2,\ldots,y_K\ (y_1 \lt y_2 \lt \cdots \lt y_K)\) にいるとします。するとこのとき、各ロボットの移動の仕方は \((\)累計での移動回数,座標\()\) を頂点とした DAG 上でのパスと見なすことができます。\(y_1 \lt y_2 \lt \cdots \lt y_K\) が成り立っていることから、すべての整数の組 \((i,j,k,l)\ (1 \leq i,j,k,l \leq K)\) について、「\(i \lt j\) かつ \(k \lt l\) ならば \((0,a_i)\) から \((N,b_l)\) に向かうパスと \((0,a_j)\) から \((N,b_k)\) に向かうパスは必ず頂点を共有する」という条件が満たされます。求めたい値は \(K\) 体のロボットが移動の最中に一度も出会わないようなものの数、すなわちパスの \(K\) 個組であって、そのうち \(i\) 番目のものの始点は \((0,x_i)\)、終点は \((0,y_i)\) であり、かつどの \(2\) つのパスも頂点を共有しないようなものの数です。太字で強調した \(2\) つの文言は、明らかに上述の LGV 公式の特殊形が使える条件そのものです。

よって \(K\) 個のロボットそれぞれの最終的な座標 \(y_1,y_2,\ldots,y_K\) を決め打ったとき、以下のことが成り立ちます。

\(K \times K\) の行列 \(X\) を以下の規則によって定める。すると、\(K\) 体のロボットの移動方法であって複数のロボットが移動の最中に出会うことのないようなものの数は、\(X\) の行列式と等しくなる。

  • \(X_{i,j}=(i\) 番目のロボットの移動方法であって、\(N\) 回の操作を終えたあとにいる座標が \(y_j\) となるようなものの個数\()=\binom{N}{y_j-x_i}\)

故に、\(y_1 \lt y_2 \lt \cdots \lt y_K\) を満たす全ての整数列 \(y\) について行列 \(X\) およびその行列式を求め、その和を取ればよいです。

しかし、\(y_i\) の値域は \(\min(x)\) 以上 \(\max(x)+N\) ですから、そのような整数列 \(y\) の個数は非常に多いです。そこで、\(y\) を決め打つ代わりに \(X\) の行列式を分解して、\(K!\) 通りある \((1,2,\ldots,K)\) の置換 \((p_1,p_2,\ldots,p_K)\) を一つずつ決め打ち、それぞれについて \(\sum_{y_1 \lt y_2 \lt \cdots \lt y_K} \prod_{j=1}^{K} \binom{N}{y_j-x_{p_j}}\) を求めることを考えます。

これは、以下のような動的計画法によって一つの置換あたり \(O(K(N+\max(x)))\) で求めることができます(\(\text{dp}[K][N+\max(x)]\) が求めたい値です)。なお、下記の漸化式においては便宜上 \(\min(x)\) が正であることを仮定しています。実際には \(\min(x)\) の値は零にもなり得るため、適宜値をズラす必要があります。

\[ dp[i][j]=\begin{cases} 1\ (i=j=0)\\ 0\ (0 \lt i,j=0)\\ dp[i][j-1]\ (i=0,0 \lt j)\\ dp[i][j-1]+dp[i-1][j-1] \times \binom{N}{j-x_{p_i}}\ (0 \lt i,j) \end{cases} \]

しかし、これでもまだ合計での計算量は \(O(K!K(N+\max(x)))\) と大きく、実行時間制限に間に合いません。そこで、置換を決め打つ過程を bit の情報で持つような bit dp を行うことを考えます。これにより計算量を \(O(2^KK(N+\max(x)))\) まで落とすことができ、これは十分高速です:

実装例 (C++)

参考までに、\(O(K!K(N+\max(x)))\) の提出コードを置いておきます:

実装例 (C++)

投稿日時:
最終更新: