T3

20 分

暴力 dfs 即可。

$m=1$

考虑在二进制上解决该问题。

因为最初只有一块蛋糕，那么这个问题就变得非常简单。

从高位向低位考虑，如果当前 $n$ 这一位为 $1$，那么就选择最小的蛋糕一直切，直到切出了当前二进制位对应大小的蛋糕。

正解

首先无解是好判断的，所有蛋糕的和小于 $n$ 就无解，否则可以把蛋糕都切成大小为 $1$。

考虑到 $n$ 很大，而且 $a_i$ 有一个 $2$ 的幂次的限制，不如在二进制下考虑问题。

因为把高位的 $1$ 往下一位拆会有 $1$ 的代价，而低位的 $1$ 向高位的合成是免费的，于是从低位向高位贪心。

假设现在贪心到了第 $k$ 位（$n$ 的二进制表示下第 $k$ 位为 $1$），如果当前存在一块蛋糕大小为 $2^k$，那么直接用了，剩下的蛋糕向高位合成（两块大小为 $2^k$ 的蛋糕可以当成一块大小为 $2^{k+1}$ 的蛋糕），保证蛋糕的充分利用。

如果不存在，怎么办呢？考虑将大的蛋糕往下面拆，找到最小的一块比 $2^k$ 大的蛋糕，往下一直切，知道切出一块大小为 $2^k$ 的蛋糕即可。

这样贪心的正确性显然，时间复杂度 $\mathcal{O}(m+\log^2 n)$。