G - Random Walk Distance 解説
by 
seekworser
\(N\) 回操作したときにちょうど位置 \(K\) にいる確率は、二項係数を用いて計算可能です。この値を \(p(N, K)\) と表すことにします。
\(N, X\) の現在値および現在の \(N, X\) に対するこの問題の答え \(ans\) と \(X\) 以下にいる確率 \(lower\) を管理することにすると、現在の状態から \(N+1, X\) の状態への遷移は
\[ ans \leftarrow ans + p(N, X)\\ lower \leftarrow lower + \frac{1}{2}(p(N, X+1) - p(N, X))\\ N \leftarrow N+1 \]
のように更新できます。また、\(N, X+1\) の状態への遷移は
\[ ans \leftarrow ans + (lower - (1 - lower))\\ lower \leftarrow lower + p(N, X+1)\\ X \leftarrow X + 1 \]
と計算できます。これらの遷移はいずれも適切に階乗やその逆元を前計算しておけば \(O(1)\) で計算可能です。また、これらの操作を逆順に行うことで \(N+1, X\) から \(N, X\) への遷移、\(N, X+1\) から \(N, X\) への遷移も書き下すことができます。
あとは、Mo’s algorithmと同様に \(N, X\) を \(N\) の含まれるバケットによってソートを行い、この順にクエリを処理することで全てのクエリに答えることができます。（通常のMo’s algorithmとは異なり、\(X\) として負の値が登場することなどがありますが、特に問題とはなりません。）
Mo’s algorithmといえば \(L, R\) の形のクエリに対して処理することが多いですが、このように一般の整数組に対して処理を行うことも可能です。類題としては以下などがあります。