题面

题意：有一堆硬币，其中金币，银币，铜币的个数分别为 \(A,B,C\) ，每次在这堆硬币中随机挑选一枚，放两个同样的硬币进去。求存在一种硬币使得这种硬币个数超过 \(100\) 的期望操作次数。
概率DP。
这道题目应当用倒推的方法，因为初始状态是 \(f_{100,j,k}=f_{i,100,k}=f_{i,j,100}=0\) 。
然后对于每种状态，我不妨设他的金银铜三种的个数为 \(x,y,z\) ，那么我选择金币的概率就是 \(\frac{x}{x+y+z}\) ，同理，选择银币，铜币的概率分别是 \(\frac{y}{x+y+z}\) 和 \(\frac{z}{x+y+z}\) 。
注意到，我选择金币的概率就是我从 \(f_{x+1,y,z}\) 推到 \(f_{x,y,z}\) 的概率（这个过程要进行一次操作），银币，铜币同理。那么我们就可以由此来写出方程了。

\[f_{x,y,z}=(f_{x+1,y,z}+1)\times \frac{x}{x+y+z}+(f_{x,y+1,z}+1)\times \frac{y}{x+y+z}+(f_{x,y,z+1}+1)\times \frac{z}{x+y+z} \]

因为我是求 \(f_{A,B,C}\) ，所以我使用了DFS（不用也能做出来），导致需要使用记忆化搜索。

代码