本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-23 09:51:40

这道题的转移方程还不算难列：

$$ 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)$ 的。

然后推出即可。