讨论区 $\LaTeX$ 挂了（似乎和剪贴板的不一样），看这个剪贴板

---

题目：P8273 [USACO22OPEN] Pair Programming G

USACO 官方题面：题面

USACO 官方题解：题解

USACO 官方题解与洛谷题解（以下统称“题解”）均能通过 USACO 给出的所有测试点并 $\color{lime}\texttt{AC}$ 本题。但是所有题解都不能按照题面的意思对一些 hack 数据给出正确的结果。

所有题解都是基于 dp 来实现的本题，并考虑了以下几点：

• $\times 0$ 之前的全部无效
• $\times 1$ 没有任何效果
• $\times a$ $\times b$ 等效于 $\times b$ $\times a$（乘法交换律）
• $+ a$ $+ b$ 等效于 $+ b$ $+ a$（加法交换律）

可以看到，题解在 dp 时预处理了前两点，并去掉了后两点引起的重复——也就是考虑了交换律带来的重复。

但是，除了交换律会带来重复，还有一种情况会引起重复：质因数分解（以及质因数同构）

即：$\times 2$ $\times 3$ 等效于 $\times 6$（质因数分解）

$\times 2$ $\times 6$ 等效于 $\times 3$ $\times 4$（质因数同构）

对于下面的 hack 数据，所有题解给出的结果都是 $9$，而实际的结果应该是 $8$（实际结果通过手动模拟题意得出）

hack：

1
3
23+
+6+

下表中，“组合”一栏表示，在这一栏中的位置填入第一个程序 23+，不在的填入第二个位置 +6+。例如 $1,4,6$ 代表了 2+63++:

$\texttt{{\color{red}1} 2 3 {\color{red}4} 5 {\color{red}6}}$

$\texttt{{\color{red}2} + 6 {\color{red}3} + {\color{red}+}}$

这个表格炸了

题解给出的结果是 $9$ 种，比实际情况 $8$ 种多了一种，那么是哪里多了呢？

可以发现，第 $11$ 种和第 $20$ 种分别为 +23+6+ 和 +6+23+。两者结果相同，不是交换律的作用，而是因为一个 $\times 2$ $\times 3$ 合并成了 $\times 6$，一个 $\times 6$ 被拆分成了 $\times 2$ $\times 3$。

事实上，如果把 $\times 6$ 换成 $\times 7$，也就是 +23+7+ 和 +7+23+，计算结果将分别为 $42x+7y+z$ 和 $42x+6y+z$，是两个不同的结果。题解结果算出来的第 $9$ 种就是这两种其中的一个。

然而，由于我太蒻了，我并不会写出完全符合题意的程序，而且 USACO 官方题解的做法也忽略了这一点，说明出题人很有可能并不希望题目包含这一点，因为考虑这一点会使难度大大增加，以至于不适合 USACO G 组。

但是对于一道题目，其正解必须对于所有合法输入给出对应的符合题面意义的输出，而不是通过其所有测试数据。在题面里面使用的大家都知道的背景（如本题的程序算术运算）时，也必须完整地引入该背景的所有规则（例如引入交换律、结合律，就要引入 $2\times 3=6$ 这种基本的“算术规则”）。因此，我的建议是：

重新设定一个题面规则，规定 $a\times b=b\times a$，$a+b=b+a$，但是 $2\times 3\neq6$，$2\times 6\neq 3\times 4$。换句话说，也就是把原先的数字 2 到 9 看成 $p_2$ 到 $p_9$，其中对于任意两个不同的可重集 $\{p_{a_1},p_{a_2},\dots,p_{a_k}\}$，都有不同的乘积。

一个便捷且符合认知的办法是，把 $p_i$ 设为不同的素数。例如下面的表格中，把 0 到 9 看成 $\times p_0$ 到 $\times p_9$。

这个表格也炸了

以上内容仅代表个人建议，本人并没有否认 USACO 官方以及洛谷的权威性和严谨性，也没有任何恶意，违规紫衫，不喜轻喷。