[ABC333F] Bomb Game 2 分析
__ryp__
·
·
个人记录
这道题的转移方程还不算难列：
f(i, j) =
\begin{cases}
\frac 1 2 f(i, i) & j = 1 \\
\frac 1 2 f(i - 1, j - 1) + \frac 1 2 f(i, j - 1) & \text{otherwise}
\end{cases}
但是问题是，这个转移方程是带环的：
\begin{aligned}
f(2, 1) = \frac 1 2 f(2, 2) \\
f(2, 2) = \frac 1 2 f(2, 1) + \frac 1 2 f(1, 1)
\end{aligned}
但是我们发现，这个方程组是有通解的：
\begin{aligned}
f(n, 1) = \dfrac {\sum\limits_{i=1}^{n - 1} 2^{i-1} \times f(n - 1, i)}{2^n - 1} \\
f(n, i) = \frac 1 2 f(n - 1, i - 1) + \frac 1 2 f(n, i - 1)
\end{aligned}
于是，f(n, 1) 的计算是 O(n) 的，而 f(n,i), \text{s.t.} \space i \neq 1 的计算是 O(1) 的。
然后推出即可。