题解

思路

先把相等关系合并成等价类。严格轻重关系在等价类之间形成有向无环图，每个类需要取 $1,2,3$ 中的一个值，且每条严格边两端至少相差 $1$。

子任务 1

枚举全部 $3^n$ 种重量赋值，过滤不满足矩阵的方案。对每个右侧砝码对记录所有合法方案中的比较符号；只有符号唯一时计数。

子任务 2

当任意两个不同砝码的关系都已知时，所有砝码按重量分成至多三个有序层级。若只有两个层级，虽然相邻层级的实际重量差可能是 $1$ 或 $2$，但天平两边都恰有两个砝码，公共的平移量与正的缩放量不会改变比较结果。因此只需给每个砝码求出所在层级，直接枚举右侧砝码对并比较层级和。

做法

用 Floyd 型最大值转移求出任意两个等价类之间最长的严格下降链长度。由向下和向上的最长链可得到每个类的绝对取值区间。

对于四个相关等价类的一组候选取值，先检查同一等价类取值一致、各自落在绝对区间内；再检查任意两个固定类之间的最长链所要求的最小差值。差分约束的传递闭包保证这些条件也是可补全的充分条件。

枚举全部候选取值，收集左、右总重量的比较符号。符号集合大小为 $1$ 时计入对应答案。

复杂度

预处理时间复杂度为 $O(n^3)$。每个砝码对枚举常数个四元组，故总时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$。

正确性说明

最长严格链长度给出了两个类之间必须满足的最小重量差；绝对上下界则对应从该类向两端可延伸的最长链。任意固定取值若违反这些条件必然不可行。若全部条件成立，按拓扑序选择不小于所有前驱下界且不超过后继上界的值即可补全，因此判定充分。枚举覆盖四个相关砝码的全部可能取值，所以最终仅在比较结果对所有合法方案一致时计数。