题解

思路

不同二的幂之和正是二进制表示，因此任意剩余非负整数都能用 popcount 个不同二的幂表示。只需决定额外选择哪些不是二的幂的阶乘。

在 $10^{12}$ 范围内只有 $3!,4!,\ldots,14!$ 共 12 个候选，可以枚举全部子集。

做法

预处理上述阶乘。枚举每个子集，求其和 sum 与元素数 count。若 sum<=n，候选答案为 count + popcount(n-sum)。取所有候选最小值。

不枚举 $0!,1!,2!$，因为它们的数值 $1,1,2$ 已经是二的幂；把它们作为额外不同数会违反“强大数互不相同”。

正确性证明

任意合法表示可分为非二幂阶乘集合与二的幂集合。算法枚举到了前一集合；固定它后，剩余值只能由不同二的幂组成，而二进制展开既存在又唯一，项数恰为其 1 位数量。因此算法对每种阶乘选择计算了最优补全。全体子集取最小覆盖所有合法表示，所得答案全局最优。

复杂度分析

阶乘候选固定为 12 个。每组测试时间复杂度为 $O(2^{12})$，额外空间复杂度为 $O(1)$。

子任务说明

• $n\le1000$ 时可枚举全部不同强大数的子集。
• $n\le10^6$ 时可用折半搜索匹配精确子集和。
• 满数据枚举阶乘子集，并用二进制位数补足余数。