这是一个关于在特定规则下最大化议会通过议案数量的策略问题。

核心要素	描述
问题目标	对每个议员 $i$ 作为议长时，通过选择合适的副议长，最大化通过的议案数。
关键观察	只有那些初始赞成票数 $cnt[j]$ 等于 $\lfloor N/2 \rfloor$ 或 $\lfloor N/2 \rfloor + 1$ 的议案 $j$，其通过与否会受到移除议长和副议长投票的影响。
核心策略	对于议长 $i$，找出那些 $cnt[j] - A_{i,j} = \lfloor N/2 \rfloor$ 的"关键议案"集合 $T_i$。最优副议长 $j$ 需要对这些关键议案投尽可能多的反对票（即 $A_{j,k}=0$）。
推荐算法	位运算预处理与高维前缀和（SOS DP），复杂度约为 O(M · 2^M + N · M)。
特殊情形	若议长 $i$ 的关键议案集合 $T_i$ 为空，则所有议案都能通过，答案为 $M$。

🔢 问题分析

议会通过的议案需要满足：除了议长和副议长，投赞成票的议员数 不少于 $\lfloor \frac{N}{2} \rfloor$。

设 $cnt[j]$ 为对议案 $j$ 投赞成票的总人数。当议长为 $i$，副议长为 $j$ 时，议案 $j$ 通过的条件是：

$$cnt[j] - A_{i,j} - A_{k,j} \geq \lfloor N/2 \rfloor $$

其中 $A_{i,j}$ 表示议员 $i$ 对议案 $j$ 的投票（1赞成，0反对）。

💡 关键步骤与解法

1. 预处理：

   • 计算每个议案 $j$ 的初始赞成票数 $cnt[j]$。
   • 将每个议员 $i$ 的投票模式编码为一个位掩码 $S_i$，其中第 $j$ 位为 $A_{i,j}$。

2. 确定关键议案：

   • 对于议长 $i$，找出所有满足 $cnt[j] - A_{i,j} = \lfloor N/2 \rfloor$ 的议案 $j$，构成集合 $T_i$。这些议案必须由副议长投反对票才能通过。

3. 寻找最优副议长：

   • 我们需要找到一个副议长 $k$ ($k \neq i$)，其投票模式 $S_k$ 在关键议案集合 $T_i$ 对应的位上为 $0$ 的数量尽可能多。这等价于 $S_k$ 是 $T_i$ 的补集的子集。
   • 为了快速查询，我们可以使用高维前缀和（SOS DP） 来预处理每个掩码对应的最大 popcount（或议员数量）。

4. 计算答案：

   • 对于议长 $i$，设其关键议案集合 $T_i$ 对应的位掩码为 $mask_i$。
   • 通过查询预处理好的数据结构，找到所有议员中（除 $i$ 自己），其投票模式 $S_k$ 是 $mask_i$ 补集的子集时，$S_k$ 与 $mask_i$ 补集的最大交集大小（即投反对票的关键议案数）。
   • 通过的议案数 = $M - |T_i| + \text{最大交集大小}$。

🧩 算法步骤

1. 计算 $cnt$ 数组：遍历所有议员，统计每个议案的赞成票数。
2. 构建位掩码：为每个议员 $i$ 计算 $S_i = \sum_{j=0}^{M-1} A_{i,j} \cdot 2^j$。
3. 预处理高维前缀和：
   • 初始化数组 $f$，其大小为 $2^M$。对于每个掩码 $x$，如果有议员 $i$ 满足 $S_i = x$，则 $f[x]$ 存储 $popcount(x)$ 或进行数量统计。
   • 进行 SOS DP 计算：对每一位 $j$，更新 $f[x] = \max(f[x], f[x \oplus 2^j])$（具体更新方式取决于我们想查询的是最大 popcount 还是存在性）。
4. 处理每个议长：
   • 对于议员 $i$，计算 $mask_i = \sum_{j \in T_i} 2^j$，其中 $T_i$ 是关键议案集合。
   • 如果 $mask_i = 0$，则答案 $ans_i = M$。
   • 否则，查询 $target\_mask = \sim mask_i$（在 $M$ 位范围内）的子集中所有可能的 $S_k$ 的最大 popcount 值 $max\_match$。则 $ans_i = M - |T_i| + max\_match$。

💎 总结

该问题的核心在于将寻找最优副议长的问题转化为在状态压缩空间下的子集查询问题，并利用高维前缀和（SOS DP） 进行优化。由于 $M \leq 20$，状态压缩是可行的。