题目描述

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

文本数据集由文本数组

$$t_1,t_2,\ldots,t_n$$

组成。每个文本 $t_i$ 是一个 token 序列。

令 $T$ 表示至少在一个文本中出现过的所有 token 构成的集合。

对于每个文本 $t_i$，还给定一个位置集合

$$L_i\subseteq\{1,2,\ldots,|t_i|\}。$$

若 $j\in L_i$，则 token $t_i[j]$ 是由 LLM 生成的；否则，它是由用户写入的。

定义上下文大小为 $k$ 的 LLM 为概率模型 $P_k$。对于任意长度在 $0$ 到 $k$ 之间、元素来自 $T$ 的序列 $w$，模型给出下一个 token 的概率分布：

$$P_k(\text{next}\mid w)。$$

对于任意合法上下文 $w$，必须满足：

$$0\le P_k(\text{next}\mid w)\le 1,$$

以及

$$\sum_{\text{next}\in T}P_k(\text{next}\mid w)=1。$$

上下文大小为 $k$ 的模型 $P_k$ 的损失函数定义为

$$\mathcal L_k(P_k)= \sum_{i=1}^{n} \sum_{j\in L_i} -\log_2 P_k\left( t_i[j]\ \middle|\ t_i[\max(1,j-k)\ldots j-1] \right)。$$

其中，$t_i[l\ldots r]$ 表示从第 $l$ 个 token 到第 $r$ 个 token 组成的子串，$t_i[1\ldots 0]$ 表示空串。

也就是说，对于每个由 LLM 生成的位置，根据它前面的至多 $k$ 个 token 构成的上下文，加入该 token 条件概率的负对数。

若某个概率为 $0$，则其负对数视为 $+\infty$。

这个损失函数称为在 LLM 生成位置上的以 $2$ 为底的交叉熵损失。损失越小，模型越好。

对于每个

$$0\le k<\max_{1\le i\le n}|t_i|,$$

求某个上下文大小为 $k$ 的模型能够达到的最小损失 $\mathcal L_k(P_k)$。

可以证明，这个最小值一定能够达到，并且不是无穷大。

输入格式

第一行包含一个整数 $n$，表示文本数量。

接下来依次给出每个文本。第 $i$ 个文本的描述如下：

1. 第一行包含一个整数 $m_i$，表示文本长度；
2. 第二行包含 $m_i$ 个字符串 $t_i[1],t_i[2],\ldots,t_i[m_i]$，表示各个 token；
3. 第三行包含一个长度为 $m_i$ 的字符串 $\ell_i$，只包含字符 U 和 L：
   • L 表示该位置由 LLM 生成；
   • U 表示该位置由用户写入。

保证每个文本的最后一个 token 都由 LLM 生成，即

$$\ell_i[m_i]=\texttt{L}。$$

输出格式

令

$$M=\max_{1\le i\le n}m_i。$$

输出 $M$ 个实数。第 $k+1$ 个数表示上下文大小为 $k$ 时的最小可能损失，其中

$$k=0,1,\ldots,M-1。$$

每个数可以输出在单独一行。

若答案的绝对误差或相对误差不超过 $10^{-6}$，则认为答案正确。

样例 1

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

样例 2

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

样例 3

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

样例 4

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

5.509775004327
4.754887502163
4.000000000000
2.000000000000

数据范围

$$1\le n\le 10^5,$$ $$1\le m_i\le 3\cdot 10^5。$$

每个 token 的长度在 $1$ 到 $5$ 之间，字符的 ASCII 编码范围为 $33$ 到 $126$。

所有文本长度之和不超过 $3\cdot 10^5$。