D

算法 1

对于每个询问暴力枚举一个二进制数判断一下是否匹配，时间复杂度 $O(q2^nn)$，期望得分 $12$。

如果只枚举每个问号填什么还可以通过 $18\sim 19$，期望得分 $20$。

如果 $q>3^n$，可以加个记忆化，时间复杂度 $O(6^n)$ 或 $O(4^n)$，据实现优秀程度可以通过 $4\sim 11$ 中前缀的测试点，期望得分 $28\sim 52$。感觉能过 $n=14$ 的话是真很会写代码了。

这里讲一下怎么分析这种暴力的时间复杂度。首先如果你的做法是暴力枚举二进制数，那没什么好分析的，不同询问个数是 $3^n$，每个询问 $O(2^n)$，总共就是 $O(6^n\rm{poly}(n))$。如果你是枚举问号，可以分析每一位有哪些可能：如果询问的是 $0/1$ 的话，查询的时候不用枚举这一位，否则相当于枚举了 ?0 和 ?1 两种，也就是说每一位有 $4$ 中情况，时间复杂度就是 $O(4^n)$。再举个例子，如果给定数组 $f_s$，求 $g_s=\sum_{t\subset s}f_t$（即求子集和），如果使用暴力的话，每一位有三种情况：s0t0，s1t1，s1t0，所以暴力时间复杂度 $O(3^n)$。

算法 2

可以考虑魔改高维前缀和。设 dp 状态：$f_{i,s,t}$ 表示我们考虑了前 $i$ 位 $(0\le i\le n)$，$s$ 表示前 $i$ 位对应的 01?，$t$ 表示后 $n-i$ 位对应的 01 的权值和。

考虑人话说法：如果一个权值 $a_S$ 满足：前 $i$ 位和 $s$ 符合，后 $n-i$ 位等于 $t$，就会把 $a_S$ 加入 $f_{i,s,t}$。

例如 $n=4$ 时：$f_{2,0?,01}=a_{0001}+a_{0101}$，$f_{3,?0?,1}=a_{0001}+a_{0011}+a_{1001}+a_{1011}$。

考虑转移，$i\rightarrow i+1$ 的时候用手枚举一下 $t$ 的第一位是保持不变还是变成问号，把这一位塞到 $s$ 里，再把 $t$ 的第一位扔掉。初始化是 $f_{0,\empty,t}=a_t$。查询答案是 $f_{n,s,\empty}$。

可以发现转移是 $O(1)$ 的，状态数是 $\sum_{i=0}^n 3^i2^{n-i}\le \sum_{i=0}^n 3^n=3^nn$。如果你不会分析或者不想分析，可以认为是 $O(3^nn)$。实际上可以分析：$\sum_{i=0}^n 3^i2^{n-i}=\sum_{i=0}^n 3^{n-i}2^i=3^n\sum_{i=0}^n(\frac{2}{3})^i\le 3^{n+1}$，所以其实是 $O(3^n)$。空间也是 $O(3^n)$。期望得分据实现优秀程度 $44\sim60$（不结合 $18\sim 19$ 的暴力）。

算法 3

我会特殊性质！

对于 $a_i=i$，相当于算所有填充方案对应二进制数和。可以独立计算每一位的贡献。时间复杂度 $O(nq)$，期望得分 $8$。

询问的 ? 至少有 $16$ 个，我也不太懂咋做，反正你枚举那四个不是 ? 的预处理一下反正能做到 $O(n^4)$，估计也没人会写就是了。如果放到算法 2 的写法里要求 $s$ 至少 $i-4$ 个问号好像好写一点。

询问不存在 1，直接套用前面魔改高维前缀和的思路，由于 $s$ 的状态数变成了 $2^i$，复杂度就是 $O(2^nn)$。期望得分 $8$。这部分对正解很重要！！！

结合前面所有做法期望得分 $92$（咋这么高来着）。

算法 4

正解有点难。

询问不存在 1 的特殊性质启发我们对 1 进行容斥。考虑只有 $1$ 个 1 的情况，不妨记为 1...。可以发现这个等价于 ?... 的答案减掉 0... 的答案。进一步考虑只有 $2$ 个 1 的情况，不妨记为 11..，可以发现这个等价于 ??.. 减掉 ?0.. 减掉 0?.. 加上 00..。

用容斥的话讲就是：枚举一个 1 的子集 $S$，钦定这一个子集必须不是 1，即必须是 0；剩下的 1 的位置没有限制，相当于 ?。可以把 1 理解成一个限制，也是容斥的对象。枚举一个子集要求不合法，剩下的没有限制。容斥系数是 $(-1)^{|S|}$。时间复杂度是 $O(2^{c_1})$，其中 $c_1$ 是 1 的个数。同时需要预处理全是 0? 的串的答案，高维前缀和即可。

记 0,1,? 的个数为 $c_0,c_1,c_2$。注意到我们对称的有了 $O(2^{c_0})$ 和 $O(2^{c_1})$ 的做法，暴力是 $O(2^{c_2})$ 的，而 $c_0+c_1+c_2=n$，所以选一个最小的跑暴力，时间复杂度 $O(2^nn+q2^{\frac n3})$。空间复杂度 $O(2^n)$。卡空间是因为原题卡了，不太懂。