我想了一小时二十分钟的 ABC D，认为答案显然是 $\sum_{i=n-1}^\infty (\frac{1}{n})^i \times i \times \text{走 i 步联通所有的方案数}$

但不知道如何求方案数。

官方题解看不懂。想请教正解是这样做的吗？如果不是，正解是怎样的？如果是，如何求这个方案数？