【算法杂谈 + 好题分享】图论中的懒标记 LazyTag 思想

有三件物品可供选择，物品甲重量为 3，物品乙重量为 8，物品丙重量为 5。有一个背包，问选择任意件物品放入背包后，背包总重为 8 的方案数。

列出所有的可能：

• 选甲，选乙，选丙；
• 选甲，选乙，选丙；
• 选甲，选乙，不选丙；
• 选甲，不选乙，选丙；
• 选甲，不选乙，不选丙；
• 不选甲，选乙，选丙；
• 不选甲，选乙，不选丙；
• 不选甲，不选乙，选丙；
• 不选甲，不选乙，不选丙。

每个物品 X 都有两种状态：选 X 或不选 X，而且每个物品的状态相互独立，直接用一个式子表达：

• （选甲 或 不选甲）且（选乙 或 不选乙）且（选丙 或 不选丙）

这个逻辑表达式包含了上面全部八种情形。这里 且 的含义是，如果 A 且 B，那么 A 必须执行，B 也必须执行。

把物品重量一并列入上面的表达式中：

• （重量为 3 或 重量为 0）且（重量为 8 或 重量为 0）且（重量为 5 或 重量为 0）

这样写虽然能表达所有的情况，但文字太多还是太麻烦了。希望选取一些数学符号，完全转化为数学表达式。

观察这个式子：

• （重量为 3 或 重量为 0）且（重量为 8 或 重量为 0）=（重量为 0）或（重量为 3）或（重量为 8）或（重量为 11）

是不是与$(a+b)(c+d)=ac+ad+bc+bd$ 极为相似？从原理上看也是合理的，加法表示若干种选择之并，乘法表示两边必须要选。所以逻辑代数中经常用$+$ 代指逻辑或，$\times$ 代指逻辑与。

现在式子是这样的：

• （重量为 3$+$ 重量为 0）$\times$（重量为 8$+$ 重量为 0）=（重量为 0）$+$（重量为 3）$+$（重量为 8）$+$（重量为 11）

重量为 3$\times$ 重量为 8 = 重量为 11，看上去是乘法，但实际是加法，如何解决？高中经常有这种问题，题目要求构造一个函数$f(t)$ 满足$f(t_{1})f(t_{2})=f(t_{1}+t_{2})$，显然取$f(t)=x^{t}$ 即可，这里$x$ 是任意正实数。

在这里，我们也可以设$f(t)=x^{t}$ 表示重量为$t$。那么式子化为：

• $(x^{3}+x^{0})(x^{8}+x^{0})(x^{5}+x^{0})$

这就把背包问题转化为一个数学表达式，所求为$x^{8}$ 的系数，表示背包总重为 8 的方案数。

$x$ 并没有什么实际意义，只是一个便于简化表达的符号，上面的式子实际是一个关于$x$ 的多项式。以快速傅里叶变换为基石的多项式算法赋予了算法竞赛选手直接操纵多项式的能力，操纵多项式是 OI 数学中极其重要的内容。