题目
题解
在正式开始题目讲解之前，我给大家出一道题目：
现在你有面额为 $1$，$2$，$4$，$8$，$16$ 的纸钞各一张，若你能从这些纸钞里任选几张形成一种组合方案，并且我们认为 $0$ 元不算有效金额，请问在全部可能的组合方案中有多少种不同的总金额？
答案是 $31$ 种。
聪明的人可能已经发现了，如果算上 $0$ 为有效金额的话，$31 + 1 = 32 = 2^5$，是 $2$ 的幂次方，我们考虑每一种纸钞只有两个状态：被我们选中、不被我们选中，那么显然我们的不同选择方案有 $2^5 = 32$ 种，正好等于我们先前的答案，也就是说实际上无论你如何选择纸钞，对于不同的选择方案，你一定不会凑出相同的总金额。
实际上这是很好证明的，我们从二进制的角度来思考这个问题，我们用 $(x)_y$ 表示 $y$ 进制下的数字 $x$，例如十进制 $21 = (21)_10$，二进制 $1001 = (1001)_2$（这里注意一下高位在左，低位在右），那么显然有 $(1)_{10} = (1)_2$, $(2)_{10} = (10)_2$, $(4)_{10} = (100)_2$, $(8)_{10} = (1000)_2$, $(16)_{10} = (10000)_2$，也就是说如果我们使用二进制来表示我们的总金额，假设我们选择了面额 $4$, $1$，那么我们的总金额为 $(00101)_2$，假设用 i, j, k, m, n 分别表示面额 1, 2, 4, 8, 16 是否被选择（选择则表示为 1，不选择则表示为 0）那么我们的总金额可以进一步表示为 $(nmkji)_2$，刚才的例子中，我们分别令 $k = 1, i = 1$, $n = 0, m = 0, j = 0$，来表示只选择面额 $4$ 和 $1$，于是总金额的表示就更直观了 $(00101)_2$ = $(5)_10$。发现了吗？我们选择之间毫不冲突，不同的选择方案一定对应着不同的总金额！以及这里还有一个拓展规律，我们注意到 $1 + 2 + 4 + 8 + 16 = 31$，正好等于我们能够凑出的合法总金额数，中间没有任何空缺，处于 $[1, 31]$ 的数字都可以在此系统下被我们组合得到！实际上，这个规律可以推广到 $n$，只要你拥有 $2^0$, $2^1$, $2^2$, …… $2^{n – 1}$, $2^n$ 这些种类的面额各一个，你就一定能凑出 $[0, 它们的和]$ 中的任意金额出来。
现在我们回到每日一题本身，我们不妨对 $x$ 的不同取值做一个分类讨论：
- 当 $x = 0$ 时，我们直接用上述结论就能解决问题。
- 当 $x = 1$ 时，我们不妨设我们的每个选择方案分为【选追加的数字】和【不选追加的数字】，于是我们可以发现，若设【不选追加的数字】的方案可以组合出 $[1, y]$ 的全部金额，追加的数字为 $z$，显然【选追加的数字】就可以组合出 $[1 + z, y + z]$ 的全部数字，显然在题目约束下 $z < y$，因此取并集得到 $[1, y + z]$。
- 当 $x = 2$ 时，同样的，我们可以认为 $x = 1$ 的全部方案是原方案，重复使用 $x = 1$ 的方法进行推广。
显然，合并以上三种分类讨论，若设 $x_1, x_2$ 为追加的数字（未追加则令其为 0），$sum = \sum_{i = 0}^{k} 2^i$，显然我们可以组合出的金额数为 $[0, sum + x_1 + x_2]$，我们只需要判断每次查询的数字与上界的大小关系便可判断是否可以组合得到这个数字。
#include <bits/stdc++.h>
using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using de = double;
using ld = long double;
using namespace std;
void solve()
{
int k, x, q; cin >> k >> x >> q;
int check = 0;
for (int i = 0; i <= k; ++i) check += (1 << i); // 1 << i 相当于 2^x
while (x--)
{
int num; cin >> num;
check += (1 << num);
}
while (q--)
{
int m; cin >> m;
if (m <= check) cout << "YES\n";
else cout << "NO\n";
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
}