CF662C Binary Table
有一个暴力思路是：枚举翻转哪些行，然后之后单独考虑翻转列了。如果当前列的 \(1\) 比 \(0\) 多，那么就翻转当前列。复杂度 \(O(2^nnm)\)。
考虑将上面的形式变得更优美，令 \(g(i)=\min(\text{popcount}(i),\text{popcount}(2^n-i))\)。
则答案为 \(\min_{S=0}^{2^n-1} \sum \limits _{i=1}^m g(sta_i\oplus S)\)。其中 \(sta_i\) 表示第 \(i\) 列的状态。考虑把 \(sta_i\) 按照值域分类，\(cnt_i\) 代表 \(sta_j=i\) 的数量。
则写成 \(\min_{S=0}^{2^n-1} \sum \limits _{i=0}^{2^n-1} g(i\oplus S)\times cnt_i\)。令 \(f(i)=\sum \limits _{j\oplus k=i} g(j)\times cnt_{k}\)。则答案为 \(\min \limits_{S=0}^{2^n-1} f(S)\)。使用 FWT 求 \(f\) 数组，复杂度 \(O(n\log n)\)。
P10242 [THUSC 2021] Emiya 家明天的饭
枚举选择的人，那么有 \(\min \limits _{S=0}^{2^n-1} \sum \limits _{i∈S}\sum \limits _{j=1}^m [S⊆T_j]a_{i,j}\)。
先枚举 \(S\)，再枚举 \(i\)，令 \(g(S,i)=\sum _{j=1}^m [S⊆T_j]a_{i,j}\)。对于每一个 \(i\)，将其所有的 \(g(S',i)\) 全部求出来，具体可以用高位前缀和或者 FWT 做。
则答案就为 \(\min \limits _{S=0}^{2^n-1} \sum \limits _{i∈S} g(S,i)\)。
CF850E Random Elections
题目可以看成 \(A\to B,B\to C,A\to C\) 进行比赛。注意到一个人最多赢两场，我们假定 \(A\) 赢两场，分别对战 \(B,C\) 选手。最后将答案乘三即可。
那么就意味着 \(f((A,B)_1,(A,B)_2,\dots,(A,B)_n)=1\) 且 \(f((A,C)_1,(A,C)_2,\dots,(A,C)_n)=1\)。其中 \((A,B)_i\) 表示第 \(i\) 个公民对 \((A,B)\) 的评价。
考虑第 \(i\) 位公民对这两场比赛的的评价为 \(P,Q\)：
- 若 \(P=1,Q=1\)，则可能的顺序为 \(ABC\) 和 \(ACB\)。
- 若 \(P=1,Q=0\)，则可能的顺序为 \(CAB\)。
- 若 \(P=0,Q=1\)，则可能的顺序为 \(BAC\)。
- 若 \(P=0,Q=0\)，则可能的顺序为 \(BCA\) 和 \(CBA\)。
则存在 \(f(x)=1,f(y)=1\)，那么 \(x,y\) 的方案数就为 \(2^{n-pop(x\oplus y)}\)。
那么答案即为 \(\sum\limits _x\sum \limits _y 2^{n-pop(x\oplus y)}\)。可以统计出 \(x\oplus y\) 的值域出现次数，使用 FWT 即可。