Description

你被给予一个文本数据集。你的任务是训练 LLM（大型语言模型）并找到可能的最小损失。不开玩笑。

一个文本数据集是一个文本数组 $t_1, t_2, \ldots, t_n$。每个文本 $t_i$ 是一个词元序列。我们将词元集合 $T$ 定义为出现在至少一个文本 $t_i$ 中的所有词元的集合。此外，对于每个文本 $t_i$，存在一个位置集合 $L_i \subseteq \{1, 2, \ldots, |t_i|\}$。词元 $t_i[j]$ 由 LLM 生成当且仅当 $j \in L_i$，由用户书写当且仅当 $j \notin L_i$。

让我们将上下文大小为 $k$ 的 LLM 定义为一个概率模型 $P_k$，它根据一个上下文 $w$（一个长度在 $0$ 到 $k$ 之间（含）且元素来自 $T$ 的序列）定义序列下一个词元的概率分布。因此概率模型 $P_k$ 是一个庞大的概率表 $P_k(\text{next} | w)$，对任意上下文 $w \in T^{*}$、$0 \leq |w| \leq k$ 和任意词元 $\text{next} \in T$ 均有定义。条件 $0 \leq P_k(\text{next} | w) \leq 1$ 和 $\sum\limits_{\text{next} \in T} P_k(\text{next} | w) = 1$ 必须满足。

上下文大小为 $k$ 的 LLM 的损失函数是为 $P_k$ 定义的如下函数：

$$\mathcal{L}_k(P_k) \,\, = \,\, \sum_{i=1}^{n} \,\, \sum_{j\in L_i} \, -\log_2 P_k\!\left( \underbrace{t_i[j]}_{\text{下一个词元}} \ \middle|\ \underbrace{t_i[\max(1,j-k)\,..\,j-1]}_{\text{上下文}} \right)$$

这里 $t_i[l\,..\,r] = t_i[l] t_i[l+1] \ldots t_i[r]$ 是从第 $l$ 个到第 $r$ 个词元的子串，$t_i[1\,..\,0]$ 是空字符串。因此，对于每个文本以及每个由 LLM 生成的词元，我们将该词元将被生成的概率的负对数（以 $2$ 为底）加到损失中，该概率依赖于前 $k$ 个词元的子串（或者如果前缀长度小于 $k$，则是整个前缀）。如果概率为零，我们假设负对数为 $+\infty$。该损失函数被称为基于 LLM 生成位置的（以 $2$ 为底的）交叉熵损失。损失函数值 $\mathcal{L}_k(P_k)$ 越小，LLM $P_k$ 越好。

对于每个 $0 \leq k < \max\limits_{i=1..n} |t_i|$，计算对于某些 $P_k$ —— 上下文大小为 $k$ 的 LLM —— 可以获得的最小可能损失 $\mathcal{L}_k(P_k)$。可以证明这个最小值是可达到的且不是无穷大。

Input Format

第一行包含一个整数 $n$ ($1 \leq n \leq 10^5$) —— 数据集中文本的数量。接下来是文本描述。

第 $i$ 个文本描述的第一行包含一个整数 $m_i$ ($1 \leq m_i \leq 3 \cdot 10^5$) —— $t_i$ 的长度 ($m_i = |t_i|$)。

下一行包含 $m_i$ 个字符串 $t_{i}[1]$, $t_{i}[2]$, $\ldots$, $t_{i}[m_i]$ ($1 \leq |t_{i}[j]| \leq 5$) —— 文本 $t_i$ 的词元。每个词元由 ASCII 码在 $33$ 到 $126$ 之间的字符（可打印字符）组成。

下一行包含一个由 $m_i$ 个字母 $\texttt{U}$ 和 $\texttt{L}$ 组成的字符串 $\ell_i$，它编码了集合 $L_i$。所有字母为 $\texttt{L}$ 的位置由 LLM 生成，所有字母为 $\texttt{U}$ 的位置由用户书写。因此 $L_i = \{j\,|\,\ell_{i}[j] = \texttt{L}\}$。保证最后一个词元由 LLM 生成，即 $\ell_{i}[m_i] = \texttt{L}$。

保证所有 $i$ ($1 \le i \le n$) 的 $m_i$ 之和不超过 $3 \cdot 10^5$。

Output Format

输出 $M = \max\limits_{i=1..n} m_i$ 个实数：对于每个 $k = 0, 1, \ldots, M-1$，输出所有可能的 $P_k$ —— 上下文大小为 $k$ 的 LLM —— 的最小可能损失 $\mathcal{L}_k(P_k)$。

如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则将被接受；形式化地说，如果 $p$ 是你的答案，$q$ 是出题人的答案，则应满足：$\frac{|p - q|}{\max\{1, |q|\}} \le 10^{-6}$。

4
5
1 + 1 = 2
UUUUL
5
1 + 2 = 3
UUUUL
5
2 + 1 = 3
UUUUL
5
2 + 2 = 4
UUUUL

6.000000000000
6.000000000000
4.000000000000
4.000000000000
0.000000000000

4
4
N E F <EOS>
LLLL
5
N E R C <EOS>
LLLLL
6
N E E R C <EOS>
LLLLLL
5
I C P C <EOS>
LLLLL

55.683674395584
12.490224995673
8.000000000000
8.000000000000
8.000000000000
8.000000000000

1
16
a b a c a b a d b a b d a b a c
ULLULLLLLLULLLLL

22.595941331507
12.464393446710
5.245112497837
2.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000

2
4
WA WA WA AC
LULL
4
AC AC WA AC
LLUL

5.509775004327
4.754887502163
4.000000000000
2.000000000000

Hint

翻译由 DeepSeek V3 完成