A

考虑逐位确定答案，答案的位数是 $\mathcal O(k+\log n)$ 的，因此可以将问题转化为 $O(k+\log n)$ 次询问形如 $\overline{x_1x_2x_3\cdots x_k?\cdots ?}$ 的数有多少种方案将 $?$ 替换为 $0\sim 8$ 使得这个数是 $10^k-1$ 的倍数。

一个数是 $10^k-1$ 的倍数当且仅当从低往高位，每 $k$ 位划为一段，所有段的和是 $10^k-1$ 的倍数。

因为段数很少（设为 $l$），不妨先枚举这个和，即 $[i(10^k-1)]_{i=0}^{l}$。接下来按照在段中的位置，从低往高数位 dp 即可。

时间复杂度 $\mathcal O(\log (n+k))$。

B：

两面一定是 $1$ 或出现过的数字，因此可以离散化。

如果不考虑买硬币的代价，两面是独立的，先求出一面是 $a$ 时的收益 $S_a$，这可以简单通过前缀和得到。

接下来需要求出 $\max_{a,b}\{S_a+S_b-ab\}$，考虑固定 $a$，发现只有在凸包上的 $b$ 有用，反之亦然。因此只保留凸包上的点，继而可以双指针。

时间复杂度 $\mathcal O(n)$。

C：

发现每次可以通过添加两个数，使得方案数 $\times2$ 或 $\times2+1$，这样可以拿到 60pts，打表 + 预处理可以优化成 75pts。

考虑构造如下由两部分组成的方案结构：

1. 序列 $(a_i)_{i=1}^n$，满足 $a_i\gt 0$。

2. 序列 $(-b_i)_{i=1}^m$，满足 $b_i\gt \frac{\sum a_i}{2}$。

这个方案的零和子集一定是空集或选出一些 $a_i$ 使得他们的和是某个 $b_j$，由这些形成 $a_i$ 和形成的 $b_j$ 的集合，因此如果固定 $a$，每个 $b_i$ 的贡献是独立的。

考虑令 $a$ 为某个优秀的常序列，预处理出每个 $x$ 如果加进 $b$ 中会对答案产生多少贡献，这可以通过背包求出，接下来考虑对于每个目标零和子集数求出方案，这同样可以用背包求出。

选择一个比较随机的 $a$ 序列可以通过，时间复杂度为 $\mathcal O(10^6\times 22)$。