题解：CF98E Help Shrek and Donkey

首先，在最优策略的条件下，在没有多余信息的情况时，先手不会主动去猜测，只会不断地尝试询问。

接下来我们尝试列出以下表格。其中，上方是先手，左侧是后手。先手询问一张自己手中没有的牌，称之为问；询问一张自己手中有的牌，称之为诈：

设 $f_{n,m}$ 表示先手有 $n$ 张，后手有 $m$ 张牌时，先手获胜的概率。对四种情况进行详细地分析：

$\texttt{Case A}$

• 有 $\frac{1}{m + 1}$ 的概率问到桌上的那张牌。由于后手选择相信，后手也就知晓了桌上的牌，因此下一次可以直接猜测这张牌而获胜。

• 有 $\frac{m}{m + 1}$ 的概率问到后手手中的牌。后手失去一张牌且无多余信息获得。

因此该种情况的收益为 $\frac{1}{m + 1} \times 0 + \frac{m}{m + 1}(1-f_{m - 1,n})$。

$\texttt{Case B}$

后手认为这张牌是桌上的牌，因此后手无法获胜，收益为 $1$。

$\texttt{Case C}$

• 有 $\frac{1}{m + 1}$ 的概率问到桌上的那张牌。由于后手选择不相信，相当于后手认为这张牌是先手的，因此先手胜。

• 有 $\frac{m}{m + 1}$ 的概率问到后手手中的牌。后手失去一张牌且无多余信息获得。

因此该种情况的收益为 $\frac{1}{m + 1} \times 1 + \frac{m}{m + 1}(1-f_{m - 1,n}) = 1 - \frac{m}{m + 1}f_{m - 1,n}$。

$\texttt{Case D}$

相当于后手知晓了先手的一张牌，先手无多余信息获得，收益为 $1 - f_{m,n - 1}$。

四种情况均已知晓后我们就需要找到纳什均衡，换句话说，就是找到一个概率 $p$ 使得每个人的选择都让对方无法猜透，更进一步来说，就是期望价值相等（如果画图，可以得到两条线存在非坐标轴处的交点）。因此可列出方程：

代码用记忆化即可，注意边界情况：

1
2
3
4
5
6
7
8
9

long double dfs (int x,int y)
{
    if (dp[x][y]) return dp[x][y];
    if (!x) return dp[x][y] = 1.0 / (y + 1);
    if (!y) return dp[x][y] = 1.0;
    long double A = 1.0 * y / (y + 1) * (1 - dfs (y - 1,x)),B = 1.0,C = 1.0 - 1.0 * y / (y + 1) * dfs (y - 1,x),D = 1 - dfs (y,x - 1);
    long double p = (B - D) / (B + C - A - D);
    return dp[x][y] = p * A + (1 - p) * B;
}