P13260 [GCJ 2014 #3] Magical, Marvelous Tour

一位神秘的电子工厂老板做了一件十分吸引人的事：她在七台电子设备中藏了金色晶体管，而购买到这些设备的人将被邀请参加一次神奇而奇妙的工厂之旅。 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 最终获得金色晶体管的概率是多少？

输入的第一行是测试用例数量 $\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$。

对于每个测试用例，输出一行，格式为 `"Case #x: y"`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Arnar 获得金色晶体管的概率。 你的输出将被认为是正确的，只要绝对误差或相对误差在 $10^{-9}$ 以内。

**样例解释** - 在第一个样例中，只有一台设备且含有一个晶体管。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 完成