P16848 [GKS 2021 #C] Binary Operator
题目描述
给定一个使用非负整数、括号 $()$、加号 $+$、乘号 $*$ 以及一个额外运算符 $\#$ 组成的合法算术表达式列表。这些表达式是**完全括号化**的，并且采用中缀表示法。
**完全括号化**的表达式是指每个运算符及其操作数都被包裹在一对括号中。
例如，表达式 $x+y$ 完全括号化后变为 $(x+y)$，而 $x+y+z$ 完全括号化后变为 $((x+y)+z)$。然而，$0$ 仍然是 $0$，因为它只包含一个数字而没有运算符。$((x+y))$ 不被认为是完全括号化的，因为它有多余的括号。
运算符 $+$ 和 $*$ 分别表示加法和乘法，而 $\#$ 可以是任意一个全函数（total function）。
你想将这些表达式分组为等价类，其中两个表达式属于同一个等价类当且仅当无论 $\#$ 代表哪个函数，它们的结果数值总是相同。
你可以假设在同一个测试用例中，$\#$ 代表同一个函数。这意味着 $\#$ 可能代表某个已知函数（如加法或减法），但在同一个测试用例的不同部分不会代表不同的函数。
例如，考虑以下表达式：
$$
\begin{aligned}
F_1&=((1\#(1+1))+((2\#3)*2))\\
F_2&=(((2\#3)+(1\#2))+(2\#3))\\
F_3&=((2*(2\#3))+(1\#2))
\end{aligned}
$$
令 $A=1\#2$，$B=2\#3$，则无论 $\#$ 代表什么函数，我们都可以将表达式重写为：
$$
\begin{aligned}
F_1&=((1\#2)+((2\#3)*2))=(A+(B*2))=(A+2B)\\
F_2&=(((2\#3)+(2\#3))+(1\#2))=((B+B)+A)=(A+2B)\\
F_3&=((2*(2\#3))+(1\#2))=((2*B)+A)=(A+2B)
\end{aligned}
$$
因此 $F_1=F_2=F_3$。
然而，考虑表达式 $F_4=((0\#0)+(0\#0))$ 和 $F_5=(0\#0)$。如果 $\#$ 表示加法，那么 $F_4=F_5$。但是，如果 $\#$ 是常数函数 $f(x,y)=C$（$C$ 为非零整数），则 $F_4 \ne F_5$，因为 $2C \ne C$。因此 $F_4$ 和 $F_5$ 不属于同一个等价类。
输入格式
输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$。随后 $N$ 行，第 $i$ 行包含一个表达式 $E_i$。
输出格式
对于每个测试用例，输出一行，格式为 `Case #x: Y1 Y2 ... YN`，其中 $x$ 是测试用例编号（从 $1$ 开始），$Y_i$ 是满足以下条件的字典序最小的序列：
1. $1 \le Y_i \le Z$，其中 $Z$ 表示该测试用例中等价类的总数。
2. $Y_i = Y_j$ 当且仅当 $E_i$ 和 $E_j$ 属于同一个等价类。
说明/提示
这个样例测试集 $1$ 包含 $3$ 个测试用例。
测试用例 $1$ 有 $7$ 个表达式，共 $2$ 个等价类，记作 $G_1$ 和 $G_2$。
$E_1=(1*(1\#2))$，$E_2=(0*(1\#2))$，$\ldots$，$E_7=(((1+(1\#2))+3)*0)$。
$E_1$、$E_3$ 和 $E_6$ 属于 $G_1$，$E_2$、$E_4$、$E_5$ 和 $E_7$ 属于 $G_2$。
在测试用例 $1$ 中，有 $2$ 个序列 $Y_i$ 满足等价类的要求：$2\ 1\ 2\ 1\ 1\ 2\ 1$ 和 $1\ 2\ 1\ 2\ 2\ 1\ 2$。
由于 $1\ 2\ 1\ 2\ 2\ 1\ 2$ 字典序更小，因此测试用例 $1$ 的输出为：`Case #1: 1 2 1 2 2 1 2`。
测试用例 $2$ 有 $5$ 个表达式，共 $2$ 个等价类，记作 $G_1$ 和 $G_2$。
$E_1$、$E_2$ 和 $E_4$ 属于 $G_1$，$E_3$ 和 $E_5$ 属于 $G_2$。
因此，测试用例 $2$ 的输出为：`Case #2: 1 1 2 1 2`。
测试用例 $3$ 有 $2$ 个表达式，它们都不包含 $\#$。
这两个表达式的计算结果相同，因此属于同一个等价类。
在所提供的样例 $2$ 中，共有 $5$ 个等价类。输入中的第一个表达式为 $((2*(2\#3))+(1\#2))$。与其属于同一等价类的所有表达式在输出中用 $1$ 表示。用 $2$ 表示的等价类包含 $(0*(1\#2))$、$0$ 和 $(3*0)$。用 $3$ 表示的等价类包含 $(1\#(2\#3))$。最后两个表达式 $(4\#7)$ 和 $(7\#4)$ 彼此不等价，也与之前的任何表达式不等价。注意，$2\ 1\ 1\ 2\ 1\ 3\ 2\ 5\ 4$ 是满足给定输入等价类要求的众多序列之一，但它不是正确答案，因为该序列不是字典序最小的。
### 限制条件
$1 \le T \le 100$
$1 \le N \le 100$
对于所有 $i$，$E_i$ 的长度至多为 $100$。
对于所有 $i$，$E_i$ 是合法的。
**测试集 1**
每个表达式中最多有一个 $\#$。
**测试集 2**
无额外限制。
翻译由 DeepSeek V4 Pro 完成