问题描述

众所周知，任何一个数 $n$ 可以拆分为若干项，这些项是不同的，由 $2$ 的次幂和 $3$ 的次幂相乘之和组成，即：

题解

这题题目要求 $2^{a_i}3^{b_i} \neq 2^{a_j}3^{b_j}$

那我们直接令所有的 $b = 0$，题目就变成了将一个 $n$ 转成 $2 ^ {a_i} + 2 ^ {a_{i + 1}} ...$，成了一个简单的二进制转换问题。

由于 $a_i$ 和 $b_i$ 的数量很有限，那么其 $a_ib_i$ 的组合数量也不多。

于是塔子哥猜测，出题人原本不是想考察这个。而是更像考察物品数量比较少，且背包容量比较大的，01背包恰好装满问题，这个可以用 最短路优化背包 的方法解决，但由于在笔试中这个难度有点超纲了，感兴趣的朋友可以自行了解。