Description

一位神秘的电子工厂老板做了一件十分吸引人的事：她在七台电子设备中藏了金色晶体管，而购买到这些设备的人将被邀请参加一次神奇而奇妙的工厂之旅。

Arnar 和 Solveig 得到线报，说他们本地的电子商店中某台设备里藏有一个金色晶体管。于是他们凑钱买下了所有的设备，并将设备排成一排，从 $0$ 到 $\mathbf{N} - 1$ 编号。每台设备中都含有若干个晶体管。他们商定了一个决定谁获得金色晶体管的策略：

首先，Arnar 选择一个区间 $[a, b]$（闭区间），其中 $0 \leq a \leq b < \mathbf{N}$，表示选中这段设备。

接下来，Solveig 可以从以下选项中选择她要的设备集：

• 如果 $a > 0$，她可以选择 $[0, a-1]$ 这一段；
• 如果 $b < N - 1$，她可以选择 $[b+1, N-1]$ 这一段；
• 她始终可以选择 $[a, b]$ 这一段。

Solveig 选择完毕后，Arnar 拿走剩下的所有设备。

例如，若设备总数为 $3$，Arnar 选择区间 $[1, 1]$，那么 Solveig 可以选择的设备段包括 $[0, 0]$、$[1, 1]$ 或 $[2, 2]$；但如果 Arnar 选择的是 $[1, 2]$，那么 Solveig 只能选择 $[0, 0]$ 或 $[1, 2]$。

在知道每台设备中晶体管数量的前提下，假设 Arnar 和 Solveig 都会选择最大化自己获得金色晶体管概率的方案（即尽可能拿晶体管总数多的设备），那么 Arnar 最终获得金色晶体管的概率是多少？

Input Format

输入的第一行是测试用例数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 行，每行包含五个整数：$\mathbf{N}$、$\mathbf{p}$、$\mathbf{q}$、$\mathbf{r}$ 和 $\mathbf{s}$。表示有 $\mathbf{N}$ 台设备，其中第 $i$ 台设备含有 $((i \times \mathbf{p} + \mathbf{q}) \bmod \mathbf{r} + \mathbf{s})$ 个晶体管。设备编号为 $0$ 到 $\mathbf{N}-1$。

Output Format

对于每个测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Arnar 获得金色晶体管的概率。

你的输出将被认为是正确的，只要绝对误差或相对误差在 $10^{-9}$ 以内。

8
1 1 1 1 1
10 17 1 7 1
2 100 100 200 1
20 17 3 23 100
10 999999 999999 1000000 1000000
2 1 1 1 1
3 1 99 100 1
999999 1000000 999999 1000000 1000000

Case #1: 0.0000000000
Case #2: 0.6111111111
Case #3: 0.0098039216
Case #4: 0.6471920290
Case #5: 0.6000006000
Case #6: 0.5000000000
Case #7: 0.0291262136
Case #8: 0.6666666667

Hint

样例解释

• 在第一个样例中，只有一台设备且含有一个晶体管。Arnar 只能选择区间 $[0, 0]$，Solveig 也只能选择这一段，因此 Arnar 不可能获得金色晶体管，概率为 $0$。
• 在第二个样例中，共 $10$ 台设备，晶体管数为：$[2, 5, 1, 4, 7, 3, 6, 2, 5, 1]$。Arnar 若选择区间 $[4, 5]$，包含晶体管为 $7$ 和 $3$ 的设备。Solveig 会选择 $[6, 9]$（总数为 $14$）而非 $[4, 5]$（总数为 $10$），那么 Arnar 将获得 $[0, 5]$，总数为 $22$，整列设备总数为 $36$，所以 Arnar 获胜概率为 $22 / 36 = 0.6111111111$。
• 在第三个样例中，两台设备分别有 $101$ 和 $1$ 个晶体管。
• 第五个样例中设备数为 $10$，晶体管数从 $1999999$ 递减到 $1999990$。

限制条件

• $1 \leq T \leq 100$
• $1 \leq \mathbf{p}, \mathbf{q}, \mathbf{r}, \mathbf{s} \leq 10^6$

Small 数据集（5 分）

• 时间限制：60 3 秒
• $1 \leq \mathbf{N} \leq 1000$

Large 数据集（8 分）

• 时间限制：120 5 秒
• $1 \leq \mathbf{N} \leq 10^6$

翻译由 ChatGPT-4o 完成