P9142 [THUPC 2023 初赛] 欺诈游戏 题解

· · 题解

做出本题不需要额外的博弈论知识，所有需要用到的已经写在题面里了。

根据输出格式，两人的策略都形如以概率 p_i 或 q_i 选取 i。

另外，输出格式中还提到：

在一方的策略不变的情况下，另一方无论如何改变自己的策略，都不能使自己的期望收益比原来多。

这样相当于是在提示，两人的策略都需要满足，无论对方选取哪个数，在自己的策略下期望收益都一致。（无法直接推出的原因，及如何正确推出见文末）

既然所有选择的期望收益一致，那么就可以根据每种情况的期望收益列方程。

对于走私者，枚举检察官的每个策略可得：

\begin{aligned}&p_1+2p_2+3p_3+4p_4+\cdots\\=&\dfrac12p_0+2p_2+3p_3+4p_4+\cdots\\=&\dfrac22p_0+\dfrac22p_1+3p_3+4p_4+\cdots\\=&\dfrac32p_0+\dfrac32p_1+\dfrac32p_2+4p_4+\cdots\\=&\cdots\end{aligned}

相邻相减，可以得到 p_1=\dfrac12p_0，2p_2=\dfrac12p_0+p_1，3p_3=\dfrac12p_0+\dfrac12p_1+\dfrac32p_2，等等。用 p_0 表示其它项，容易算出 p_k=\dfrac12p_0(k\ge 1)。

对于检察官，枚举走私者的每个策略可得：

\begin{aligned}&\dfrac12q_1+\dfrac22q_2+\dfrac32q_3+\dfrac42q_4+\cdots\\=&q_0+\dfrac22q_2+\dfrac32q_3+\dfrac42q_4+\cdots\\=&2q_0+2q_1+\dfrac32q_3+\dfrac42q_4+\cdots\\=&3q_0+3q_1+3q_2+\dfrac42q_4+\cdots\end{aligned}

相邻相减，可以得到 \dfrac12q_1=q_0，\dfrac22q_2=q_0+2q_1，\dfrac32q_3=q_0+q_1+3q_2，等等。用 q_0 表示其它项，用以上式子的规律，记录一个前缀和即容易进行递推。

最后，各个 p_i,q_i 是概率，因此要满足 \sum p_i=\sum q_i=1。结合前面算出的比例信息，即可回带算出各个 p_i,q_i。

核心部分的代码，仅供参考：

//F(i,a,b) = for(int i=a;i<=b;i++)
//ni(i) 表示求 i 在模意义下的乘法逆
p[0]=2;F(i,1,n) p[i]=1;
q[0]=1;q[1]=2;ll sum=0;
F(i,2,n)
{
    sum=(sum+q[i-2])%mod;
    q[i]=(q[i-1]*2+sum*2*ni(i))%mod;
}
sum=0;F(i,0,n) sum+=p[i];sum%=mod;sum=ni(sum);F(i,0,n) p[i]=p[i]*sum%mod;
sum=0;F(i,0,n) sum+=q[i];sum%=mod;sum=ni(sum);F(i,0,n) q[i]=q[i]*sum%mod;

题面给出的最重要的信息是，两人的最优策略都是纯概率策略。

这个条件貌似牵扯到一些类似于纳什均衡的东西，但是我又不学概率论我怎么知道.jpg

为什么引用的条件无法直接推出每种策略的期望全部相等？

因为双方有可能“放弃”对手的一部分选项，只保证对手选剩余的选项时期望全部相等（且低于对手选其它选项的期望）。

为了排除这种情况，只需要证明，这种情况下最终会得到一个比上面的策略低的期望即可。

一个简单的想法是，将对手每种选项的期望的式子进行加权平均，并让得到的结果各项系数相等，就可以利用各情况概率和为 1，得到最大值不小于/最小值不超过此平均，且当且仅当各个期望全部相等时取到等号。

为了保证上述论断成立，各个式子的权必须都是正数。

实际上，求解这个系数的方程组，与求解对手的各操作概率的方程组，是完全一样的；而后者有一个全正数解，因此前者也有。

读者可以尝试自行带入后者求出的解计算前者。