很显然，这道题目可以借助“分手是祝愿”这道题目的思想，设出\(f[i]\)表示当前状态有\(i\)个最终状态的字符，达到最终状态的期望步数
然后我们就开开心心地写出以下方程A_{i}1A_{n-i}1
\[f[i]=1+\frac{A_{n-i}^2}{A_n^2}f[i]+\frac{A_{i}^2}{A_n^2}f[i]+\frac{\sum p}{A_n^2}f[i+1]+\frac{\sum p}{A_n^2}f[i-1] \]以上方程的每一部分比较好懂，就不解释了。注意这道题目要用排列数而不是组合数，因为魔法变动的方向是单方向的。这里的\(\sum p\)指我选出来的每一对\((a,b)\)的\(p_{a,b}\)的和
然后我们似乎发现这跟状态有关了，因为\(p_{a,b}\)不同
真的是这样吗？实际上这道题目的\(p\)都为\(1\)（属实坑）
于是我们有
\[f[i]=1+\frac{A_{n-i}^2}{A_n^2}f[i]+\frac{A_{i}^2}{A_n^2}f[i]+\frac{A_{i}^1A_{n-i}^1}{A_n^2}f[i+1]+\frac{A_{i}^1A_{n-i}^1}{A_n^2}f[i-1] \]然后你就会发现推不走了。因为你觉得\(f[0]\)为多少呢？正无穷？就算我采用“分手是祝愿”这道题目的定义方法，仍然逃不过这个问题。但是如果\(f[0]\)为正无穷的话，根据公式\(f\)都为正无穷，显然不可能
所以这就是这道题目与一般的无穷嵌套DP不同的地方了。其他地方尽管可能进行无数次，但是在任何一个状态下，我一定是存在有限步来达到最终解的，而这道题目，对于\(f[0]\)来说，我无论怎么变换，都不可能达到最终的状态（这已经跟反复进行无穷步没有什么关系了），所以这就是这道题目的特殊的地方了
像这种题目，我们必须先将可能成功的概率求出来（这也就是为什么题解要求成功的概率的原因）
然而具体的期望方程是怎么推导的，我并不太清楚
标签：frac,小铃,sum,烦恼,1A,无穷,题目,这道 From： https://www.cnblogs.com/dingxingdi/p/18077262