题目内容

在一个由 $N$ 个信号源构成的通信系统中，每个离散时刻系统会按转移矩阵从一个信号源跳转到另一个，并在当前信号源上按输出矩阵生成一种波形。

现在给定：

• 初始分布向量 pi（长度为 $N$），表示系统初始位于各个信号源的概率；
• 转移矩阵 A（$N \times N$），其中 $A[i][j]$ 表示从信号源 $i$ 转移到信号源 $j$ 的概率；
• 输出矩阵 B（$N \times M$），其中 $B[i][k]$ 表示信号源 $i$ 生成波形 $k$ 的概率（波形编号为 $0,1,\dots,M-1$）；
• 以及 $S$ 条观测序列 obs，每条序列由若干个波形编号组成的整数列表。

所有概率矩阵的行均已归一化，无需再次校验。 请为每一条观测序列找出一个最可能的信号源序列（即与观测序列联合概率最大的路径），并计算该联合概率的自然对数（对数概率）。所有计算必须在对数域进行，以累积对数概率的形式实现动态规划，避免浮点下溢。最终对数概率需四舍五入保留 $6$ 位小数。

约束：信号源数量 $N \le 4$，波形种类 $M \le 4$，每条序列长度不超过 $6$，序列总数 $S \le 10$。

输入描述

输入只有一行，一个 JSON 字符串，包含以下字段：

• "pi"：浮点数数组，长度为 $N$，表示初始分布；
• "A"：浮点数二维数组，大小为 $N \times N$，表示转移矩阵；
• "B"：浮点数二维数组，大小为 $N \times M$，表示输出矩阵；
• "obs"：由整数数组构成的列表，每个整数数组代表一条观测序列。

输出描述

输出一行 JSON 字符串，包含两个字段：

• "paths"：一个列表，其中每个元素是一条最优信号源序列（整数数组）；
• "logp"：一个列表，包含各序列对应的对数概率，每个值已四舍五入到 $6$ 位小数。

样例1

输入

{"pi":[1.0],"A":[[1.0]],"B":[[1.0]],"obs":[[0]]}

输出

{"paths": [[0]], "logp": [0.0]}

说明

系统中仅有 1 个信号源和 1 种波形，所有概率均为 1.0。无论观测序列如何，系统始终停留在信号源 0 并生成波形 0，联合概率为 1，自然对数 $\ln(1) = 0$。四舍五入保留六位小数为 0.0，最优路径为 [0]。本样例验证了最小规模的边界情况。

样例2

输入

{"pi":[0.5,0.5],"A":[[0.5,0.5],[0.5,0.5]],"B":[[1.0],[1.0]],"obs":[[0,0]]}

输出

{"paths": [[0, 0]], "logp": [-1.386294]}

说明

模型有 2 个信号源和 1 种波形，所有发射概率均为 1.0，初始分布和转移矩阵均为均匀分布。因此任意长度为 2 的状态序列联合概率均为 $0.5 \times 1.0 \times 0.5 \times 1.0 = 0.25$，对数 $\ln(0.25) \approx -1.386294$。 当多条路径拥有相同的最优对数概率时，Viterbi 算法通过 $\text{argmax}$ 选择索引最小的前驱，最终回溯得到路径 [0, 0]。本样例展示了多最优路径情况下的选择规则。