【cf662C】C. Binary Table（FWT）

传送门

题意：
给出一个(n)行(m)列的(01)矩阵，每次可以选择任一行或者任一列对其进行翻转。
问进行任意次操作过后，矩阵中(1)最少的个数为多少。
(nleq 20,mleq 100000)。

思路：
行数这么少，我们可以直接考虑状压枚举行的状态，固定行的状态过后，每一列就贪心选择(0/1)个数最少的情况累加到答案中去。
我们用式子表示出来，设(f_{sta})为行数状态为(sta)时的答案，(g_{sta})表示一列状态为(sta)时最优的答案，(h_{sta})表示多少列的状态为(sta)。那么就有：

[f_{sta}=sum_{i=0}^{2^n-1}h_icdot g_{ioplus sta} ]

显然这就是一个异或卷积，我们(FWT)跑一下就行。
这种对值来进行卷积的操作还是挺常见的。
代码如下：

/*
 * Author:  heyuhhh
 * Created Time:  2020/4/23 18:15:48
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
  template <template<typename...> class T, typename t, typename... A> 
  void err(const T <t> &arg, const A&... args) {
  for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
  #define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 20, M = 1e5 + 5;

ll f[1 << N], g[1 << N], h[1 << N];

char s[N][M];

void FWT_xor(ll *a, int n, int op) {
    for(int i = 1; i < n; i <<= 1)
        for(int p = i << 1, j = 0; j < n; j += p)
            for(int k = 0; k < i; k++) {
                ll X = a[j + k], Y = a[i + j + k];
                a[j + k] = X + Y; a[i + j + k] = X - Y;
                if(op == -1) a[j + k] = a[j + k] / 2, a[i + j + k] = a[i + j + k] / 2;
            }                
}

void run() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < 1 << n; i++) {
        int cnt = __builtin_popcount(i);
        g[i] = min(cnt, n - cnt);
    }
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    for (int j = 0; j < m; j++) {
        int x = 0;
        for (int i = 0; i < n; i++) {
            if (s[i][j] == '1') x += (1 << i);
        }
        ++f[x];
    }
    int l = 1 << n;
    FWT_xor(f, l, 1), FWT_xor(g, l, 1);
    for (int i = 0; i < l; i++) h[i] = f[i] * g[i];
    FWT_xor(h, l, -1);
    ll ans = 1e18;
    for (int i = 0; i < l; i++) {
        ans = min(ans, h[i]);   
    }
    cout << ans << '
';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}