题解

本题使用高维前缀和（FMT）+ 容斥原理 + DFS枚举求解子集查询问题。

算法思路：

1. 预处理高维前缀和：

   • f[S]：子集 $S$ 的高维前缀和（对于所有 $T \subseteq S$，累加 $a[T]$）
   • g[S]：子集 $S$ 的高维后缀和（对于所有 $T \supseteq S$，累加 $a[T]$）
   • 使用FMT（Fast Möbius Transform）在 $O(n \cdot 2^n)$ 时间内计算

2. FMT算法：

   • 对于每一位 $i \in [0, n-1]$：
     • 如果状态 $S$ 的第 $i$ 位为 $1$，则 $f[S] += f[S \oplus 2^i]$
   • 对于 g 数组，反向操作：$g[S \oplus 2^i] += g[S]$

3. 查询策略选择：

   • 统计模式串中 ?、0、1 的数量
   • 选择数量最少的字符作为枚举对象（减少枚举量）
   • 三种策略：
     1. 枚举 ?：直接DFS枚举所有可能的匹配位置
     2. 枚举 0：使用 g 数组和容斥原理
     3. 枚举 1：使用 f 数组和容斥原理

4. 容斥原理应用：

   • 对于模式串，将 ? 固定为某个值后，统计包含该模式的所有状态
   • 使用容斥：枚举 0 的位置，奇数个取负，偶数个取正

5. DFS枚举：

   • 递归构造匹配的状态
   • 参数 s 表示是否需要取负（容斥符号）
   • 到达叶子节点时累加或减去对应的前缀和值

时间复杂度：预处理 $O(n \cdot 2^n)$，每次查询 $O(2^{\min(x, y, z)})$

这是一道高维前缀和与容斥原理结合的经典问题。

#include <bits/stdc++.h>

using namespace std;

// #define USE_INT_128

#define il inline
#define mkp make_pair
#define fi first
#define se second
#define ssz(x) (signed((x).size()))
#define beg2ed(x) (x).begin(), (x).end()
#define _loop_i_t(j, k) make_signed_t<decltype((j) - (k))>
#define For(i, j, k) for (_loop_i_t(j, k) i = (j); i <= (k); ++i)
#define ForDown(i, j, k) for (_loop_i_t(j, k) i = (j); i >= decltype(i)(k); --i)
#define eb emplace_back
#ifndef ONLINE_JUDGE
#define FileIO(filename)                                                       \
  freopen(filename ".in", "r", stdin);                                         \
  freopen(filename ".out", "w", stdout)
#else
#define FileIO(filename) void(0)
#endif

#define $ get
#define $0 get<0>
#define $1 get<1>
#define $2 get<2>
#define $3 get<3>

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef USE_INT_128
using lll = __int128_t;
using ulll = __uint128_t;
#endif

// clang-format off
constexpr il ll qpow(ll x, ull y, ll mod){ ll ans = 1; x %= mod; while (y) { if (y & 1) (ans *= x) %= mod; (x *= x) %= mod; y >>= 1; } return ans; }
template<typename T> constexpr il void cmin(T &x, const T &y){ x = min(x, y); }
template<typename T> constexpr il void cmax(T &x, const T &y){ x = max(x, y); }
// clang-format on

// File head end

namespace {
constexpr int MAXN = (1 << 20) + 5;
int n, Q, f[MAXN], g[MAXN];
char a[MAXN], T[25];
void Main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> Q >> a;
  For(i, 0, (1 << n) - 1) f[i] = g[i] = a[i] - '0';
  For(i, 0, n - 1) For(S, 0, (1 << n) - 1) {
    if (S >> i & 1)
      f[S] += f[S ^ 1 << i], g[S ^ 1 << i] += g[S];
  }
  while (Q--) {
    cin >> T;
    int x = count(T, T + n, '?'), y = count(T, T + n, '0'),
        z = count(T, T + n, '1'), Ans = 0;
    if (x <= y && x <= z) {
      auto dfs = [&](auto &&self, int i, int v) -> void {
        if (i == n)
          return Ans += a[v] - '0', void();
        if (T[i] == '?')
          self(self, i + 1, v << 1), self(self, i + 1, v << 1 | 1);
        else
          self(self, i + 1, v << 1 | (T[i] - '0'));
      };
      dfs(dfs, 0, 0);
    } else if (y <= x && y <= z) {
      auto dfs = [&](auto &&self, int i, int v, bool s) -> void {
        if (i == n)
          return (s ? (Ans -= g[v]) : (Ans += g[v])), void();
        if (T[i] == '0')
          self(self, i + 1, v << 1, s), self(self, i + 1, v << 1 | 1, s ^ 1);
        else if (T[i] == '1')
          self(self, i + 1, v << 1 | 1, s);
        else
          self(self, i + 1, v << 1, s);
      };
      dfs(dfs, 0, 0, 0);
    } else {
      auto dfs = [&](auto &&self, int i, int v, bool s) -> void {
        if (i == n)
          return (s ? (Ans -= f[v]) : (Ans += f[v])), void();
        if (T[i] == '1')
          self(self, i + 1, v << 1 | 1, s), self(self, i + 1, v << 1, s ^ 1);
        else if (T[i] == '0')
          self(self, i + 1, v << 1, s);
        else
          self(self, i + 1, v << 1 | 1, s);
      };
      dfs(dfs, 0, 0, 0);
    }
    cout << Ans << '\n';
  }
}
} // namespace

signed main() { return Main(), 0; }