题解：这题难度思维还是有点大，如果要靠自己想出来的话。
题意就是n*m的矩形，每次可以反转一行或者一列，无数次。问最少的1的个数。
n<=20 m<= 1e5
这就有意思了，n<=20，这一看就是想让我们状压嘛。。
直接把20行每一列压成一个二进制数f[i]。
同时之前学位运算的时候我们知道，异或0表示不变，异或1表示取反，那么我们行操作就相当于每一个a[i]都异或行那一位的1，其他位保持0就可以了。
对于列，一列翻转前后只有两种结果，所以我们可以设f[i]表示列a[i]翻转前后最少有多少个1！这里C++自带函数可以统计二进制1的个数，当然自己手写也可以。
__builtin_popcount(x)那么我们可以得到一个初步的做法：枚举K a n s ( k ) = ∑ i = 0 m − 1 f [ a [ i ] ⨁ k ] ans(k) = \sum_{i=0}^{m-1}f[a[i]\bigoplus k] ans(k)=∑i=0m−1f[a[i]⨁k]
但是这样枚举K，每次计算 o ( m ) o(m) o(m)太慢了，所以就想办法加速。
考虑转换一下式子，对于所有 a [ i ] ⨁ k a[i]\bigoplus k a[i]⨁k相同的数来说，他们对答案的贡献是一样的。同时对于枚举的K，K是相同的。所以只要提前预处理a[i]的个数就可以把式子改写为： ∑ f [ a [ i ] ⨁ k ] ∗ n u m [ a [ i ] ] \sum {f[a[i]\bigoplus k] * num[a[i]]} ∑f[a[i]⨁k]∗num[a[i]] 这时候就需要一点思维的技巧了，因为 a [ i ] ⨁ k ⨁ a [ i ] = k a[i]\bigoplus k \bigoplus a[i] = k a[i]⨁k⨁a[i]=k 所以我们可以大力改写！ ∑ i ⨁ j = k f [ i ] ∗ n u m [ j ] \sum_{i\bigoplus j=k}{f[i]*num[j]} ∑i⨁j=kf[i]∗num[j] 其中i,j的含义就是刚才括号内的含义。 有了这个式子就可以跑一遍FWT求出所有的 a n s ( k ) ans(k) ans(k) 了！
现在我们考虑一下fwt的Len，因为其中涉及到的是a[i],那么上限应该就是a[i]的上限，a[i]是n位状压而成，最大值是(1<<n)-1 所以令Len=(1<<n)即可。
预处理f[i]和num[i]都很简单
for(int i = 0;i < m;i ++)//预处理Num { tong[a[i]] ++; } for(int i = 0;i < len;i ++) f[i] = min(__builtin_popcount(i),n-__builtin_popcount(i));//预处理f完整代码
#include <bits/stdc++.h> #define mem(a,b) memset((a),(b),sizeof(a)) using namespace std; typedef long long ll; const ll INF = 10000000000000000; const int N = (1<<20) + 10; const ll mod = 1e9+7; void fwt(ll a[],int n){ for(int d=1;d<n;d<<=1){ for(int m=d<<1,i=0;i<n;i+=m){ for(int j=0;j<d;j++){ ll x=a[i+j],y=a[i+j+d]; a[i+j] = (x + y), a[i+j+d] = x - y; } } } //xor : a[i+j] = x + y, a[i+j+d] = (x - y + mod) % mod; //and : a[i+j] = x + y; //or : a[i+j+d] = x + y; } ll inv2; void ifwt(ll a[],int n){ for(int d=1;d<n;d<<=1){ for(int m=d<<1,i=0;i<n;i+=m){ for(int j=0;j<d;j++){ ll x=a[i+j],y=a[i+j+d]; a[i+j] = (x + y)/2, a[i+j+d] = (x - y)/2; } } } //inv2 = 2^(-1) //xor : a[i+j] = (x + y) / 2, a[i+j+d] = (x - y) / 2; //and : a[i+j] = x - y; //or : a[i+j+d] = y - x; } ll a[N],f[N],tong[N]; char s[N]; int main(){ inv2 = 1ll*(mod+1ll)/2ll;//2的逆元 int n,m; scanf("%d%d",&n,&m); getchar(); for(int i = 1;i <= n;i ++) { scanf("%s",s); for(int j = 0;j < m;j ++) { a[j] = ((a[j] << 1) | (s[j] - '0')); } } int len = 1 << n; for(int i = 0;i < m;i ++)//预处理Num { tong[a[i]] ++; } for(int i = 0;i < len;i ++) f[i] = min(__builtin_popcount(i),n-__builtin_popcount(i));//预处理f fwt(tong,len); fwt(f,len); for(int i=0;i<len;i++) { f[i] = f[i] * tong[i]; } ifwt(f,len); ll minn = INF; for(int i = 0;i < len;i ++) { minn = min(minn,f[i]); } printf("%lld\n",minn); } /* 3 7 4 13 */