题解：P1297 [国家集训队] 单选错位

Nagato_ · 2025-03-08 12:33:10 · 题解

显然，做对一道题的要求是：前一位的选项等于后一位的选项。

对于两个选项个数 x，y，有以下情况

若 x=y，P=\sum_{i=1}^{x}\displaystyle \frac{1}{x}\times\displaystyle \frac{1}{y}=\displaystyle \frac{1}{x}

若 x>y，则要先保证在范围内，有 P=\displaystyle \frac{y}{x}\displaystyle \times \frac{1}{y}=\frac{1}{x}

若 x<y，则要先保证在范围内，有 P=\displaystyle \frac{x}{y}\displaystyle \times \frac{1}{x}=\frac{1}{y}

于是 P=\displaystyle \frac{1}{max(x,y)}，对每一项都是这个概率。

于是，对每一个选项，有 P 的概率 f_i=f_{i-1}+1，1-P 的概率 f_i=f_{i-1}，综合起来，得到转移式子