P16423 [IATI 2022] Fork

Luca 打开了一个 Python 终端并执行了 `os.fork()`，该操作派生出了第二个终端。之后，每当 Luca 按下任意按键时，该按键会随机进入两个终端中的一个。每个终端都有一个输入字符串（显示在界面上），该字符串会根据进入该终端的按键而进行编辑。此外，Luca 能够看到终端界面，因此他在按下按键时，知道该按键影响了哪一个终端的输入字符串。 他的键盘上有 $N$ 个印有互不相同字符的按键，以及一个退格键 (Backspace)。当一个字符按键进入某个终端时，该字符会被直接追加到其输入字符串的末尾。当退格键进入某个终端时，其输入字符串的最后一个字符会被删除。如果该终端的输入字符串为空，则什么也不会发生（尽管 Luca 仍能看到退格键进入了该终端）。每次按键都有概率 $P$ 进入左侧终端，概率 $1 - P$ 进入右侧终端。 Luca 希望在两个终端中都键入某个由 $N$ 个互不相同字符组成的固定字符串 $a_1 a_2 \dots a_N$。他已经在左侧终端正确键入了前 $L$ 个字符，在右侧终端正确键入了前 $R$ 个字符（即两个终端中的字符串分别为 $a_1 a_2 \dots a_L$ 和 $a_1 a_2 \dots a_R$）。例如，考虑 $P = 0.3$，$N = 2$（目标字符串可以是 `ab`），$L = 0$，$R = 1$。一种可能的事件序列如下： | 步骤 | 按键 | 进入终端 | 左侧终端 | 右侧终端 | |:----:|:--------:|:------:|:----------:|:-----------:| | 0 | - | - | - | a | | 1 | b | 右侧 | - | ab | | 2 | a | 右侧 | - | aba | | 3 | a | 左侧 | a | aba | | 4 | b | 右侧 | a | abab | | 5 | 退格 | 右侧 | a | aba | | 6 | 退格 | 左侧 | - | aba | | 7 | 退格 | 左侧 | - | aba | | 8 | 退格 | 右侧 | - | ab | | 9 | a | 左侧 | a | ab | | 10 | b | 右侧 | a | abb | | 11 | b | 左侧 | ab | abb | | 12 | 退格 | 右侧 | ab | ab | 总计，为了让两个终端都成功键入 `ab`，花费了 $12$ 次按键。 我们将“错误字符”定义如下：存在于两个终端之一的，且在两个终端都完成整个目标字符串的键入之前的某个时刻必须被删除的字符。Luca 决定，**如果至少一个终端中不存在错误字符，他绝不会按下退格键**。他还决定，**绝不会按下一个必定会立即产生错误字符的按键**。Luca 想知道，在这些约束下他的最优策略是怎样的。具体而言，他想知道最小的期望（平均）按键次数是多少。请通过编写程序 `fork.cpp` 来解决该问题，帮助 Luca。

你的程序应从标准输入的第一行（也是唯一一行）读取四个整数 $P$、$N$、$L$ 和 $R$。

在标准输出的第一行（也是唯一一行），你的程序应打印计算得到的答案，建议输出至少 $12$ 位精度的数值。你可以使用：`std::cout

### 数据范围 - $0 \le L, R \le N \le 2 \times 10^7$ - $0.1 \le P \le 0.9$ ### 子任务与评分 | 子任务 | 分值 | $N \le$ | |:------:|:----:|:--------------:| | $1$ | $15$ | $5$ | | $2$ | $10$ | $15$ | | $3$ | $10$ | $35$ | | $4$ | $15$ | $100$ | | $5$ | $15$ | $450$ | | $6$ | $15$ | $1500$ | | $7$ | $15$ | $10^6$ | | $8$ | $5$ | $2 \times 10^7$ | 要获得给定子任务的分数，你的解答必须成功通过该子任务及所有之前子任务的全部测试数据。要通过一个测试，你的解答输出的答案相对误差不能超过 $10^{-8}$，即： $$ \frac{|\text{yourAns} - \text{trueAns}|}{\text{trueAns}} \le 10^{-8} \ (\text{其中 } \frac{0}{0} = 0) $$ 翻译由 DeepSeek V4 Pro 完成