題目鏈接
solution
因為\(n\)比較小，所以我們可以\(2^n\)列舉每一行是不是翻轉，然后對于每一列答案就唯一了，
對于每一列狀態壓縮，用\(B[i]\)表示\(i\)這個狀態最小的\(1\)的個數(也就是這個狀態里0和1更少的那個)，然后我們如果想把一列從狀態\(x\)變成狀態\(y\)，那么我們需要操作的行就是\(x\otimes y\)，用\(A[i]\)表示\(i\)這個狀態的數量，用\(ans_x\)表示操作的行為\(x\)這個狀態的時候的答案，就有\(ans_x=\sum\limits_{i\otimes j=x}A[x]B[y]\)，用\(FWT\)優化即可，
code
/*
* @Author: wxyww
* @Date: 2020-04-26 10:45:28
* @Last Modified time: 2020-04-26 11:21:07
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 1 << 20;
// #define int ll
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1; c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0'; c = getchar();
}
return x * f;
}
char s[N];
int n,m;
void FWT(ll *a,int xs) {
for(int i = 0;i < n;++i) {
for(int j = 0;j < (1 << n);++j) {
if((j >> i) & 1) continue;
ll l = a[j],r = a[j | (1 << i)];
a[j] = l + r;a[j | (1 << i)] = l - r;
}
}
if(xs == -1)
for(int i = 0;i < (1 << n);++i)
a[i] /= (1 << n);
}
ll a[N],cnt[N],A[N],B[N];
int main() {
n = read(),m = read();
for(int i = 1;i <= n;++i) {
scanf("%s",s + 1);
for(int j = 1;j <= m;++j)
a[j] = (a[j] << 1) | (s[j] - '0');
}
for(int i = 1;i <= m;++i) A[a[i]]++;
for(int i = 0;i < (1 << n);++i) {
cnt[i] = (cnt[i >> 1]) + (i & 1);
B[i] = min(cnt[i],n - cnt[i]);
}
FWT(B,1);FWT(A,1);
for(int i = 0;i < (1 << n);++i) A[i] = A[i] * B[i];
FWT(A,-1);
ll ans = n * m;
for(int i = 0;i < (1 << n);++i) {
ans = min(ans,A[i]);
}
cout<<ans;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/33446.html
標籤：C++
下一篇：樹狀陣列