SP5104 SPAMD - Spam Detection

众所周知，「free」这个词语的出现次数可以用来区分垃圾邮件和非垃圾邮件。你的任务是基于邮件中「free」出现的次数设计一个垃圾邮件检测模块。这个模块的核心是一个垃圾邮件分类器，定义为两个变量 $Low$ 和 $High$。如果邮件中包含 $X$ 个「free」单词，并且 $Low \le X \le High$，则该邮件将被视为垃圾邮件。 为了评估分类器的效果，我们引入了一些信息检索中的术语： | 实际情况 | 垃圾邮件 | 非垃圾邮件 | |:--------:|:-------:|:---------:| | 预测结果 | TP（真正例）| FP（假正例） | | | FN（假负例）| TN（真负例） | TP 是正确预测为垃圾邮件的邮件数量；FN 是错误预测为非垃圾邮件的邮件数量，其他情况以此类推。 我们用精确率（P）表示正确识别垃圾邮件的比例，公式为：$P = \frac{TP}{TP + FP}$。 召回率（R）则表示成功识别垃圾邮件的比例，公式为：$R = \frac{TP}{TP + FN}$。为了在精确率和召回率之间取得平衡，我们使用 F 值，其公式为：$F = \frac{2 \times P \times R}{P + R}$。 举个例子，当 TP = 5, FP = 3, FN = 2, TN = 4 时，R = 5/7，P = 5/8，F = 2/3。 在没有垃圾邮件的情况下，我们可以将所有邮件标记为非垃圾邮件，F 值为 1.0，代表完美的分类器。 我们的数据挖掘团队已经手动分析了一些邮件，并将它们标记为垃圾邮件或非垃圾邮件。你的任务是找到使分类效果（F 值）最佳的 $Low$ 和 $High$ 值。

输入由多个测试用例组成，每个用例包含两行： - 第一行是整数 $N$，表示某个邮件中「free」词语的最大数量（$1 \le N \le 10^6$）。 - 第二行包含四个整数 $a_0, A, B, M$，是随机数生成器的参数（$2 \le a_0, A, B, M \le 10^9$）。 随机数生成器生成的数列为： $$a_i = (A \times a_{i-1} + B) \mod M \text{ 对 } i \ge 1$$ 定义如下： $$\text{pos}_i = a_{2i} \quad (0 \le \text{pos}_i < N)$$ $$\text{neg}_i = a_{2i+1} \quad (0 \le \text{neg}_i < N)$$

对于每个用例，输出能获得最佳 F 值的分类器的 F 度量（保留到小数点后 6 位）。

- $1 \le N \le 10^6$ - $2 \le a_0, A, B, M \le 10^9$ **样例输入** ``` 3 1 1 1 3 5 2 3 4 5 ``` **样例输出** ``` 0.666667 0.923077 ``` **样例解释** 在第一个测试用例中，随机数生成器产生的序列为 1, 2, 0, 1, 2, …。垃圾邮件的数量为 $\text{pos}_i = \{1, 0, 2, 1\}$，非垃圾邮件为 $\text{neg}_i = \{2, 1, 0, 2\}$。 最优的分类器将「free」词数在 2 到 3 之间的邮件视为垃圾邮件，此时 R = 3/4，P = 3/5，结果 F = 2/3。另一种生成最优分类器的方法是仅将包含 2 个「free」词的邮件视为垃圾邮件。 **本翻译由 AI 自动生成**