0%

「Codeforces #662C」Binary Table

Codeforces #662C

题意

给出一个$n$行$m$列的$01$矩阵,可以任意次取反一行或一列,最小化矩阵中$1$的总数

$n\le20,m\le10^5$


分析

由于 $n$ 非常小,考虑状压,把 $m$ 列看成 $m$ 个 $n$ 位二进制数

同时也用一个 $n$ 位二进制数 $s$ 表示取反了的行

对于一个被表示为 $x$ 的列

  • 若不选择取反,对答案的贡献是 ${\rm popcount}(x \oplus s)$

    其中 ${\rm popcount}(t)$ 表示 $t$ 二进制中为 $1$ 的位数,$\oplus$ 表示异或

  • 若取反,则为 $n-{\rm popcount}(x \oplus s)$。

由于列之间是独立的,可以贪心选择,记 $g_i=\min({\rm popcount}(i),n-{\rm popcount}(i))$

记$f_i$表示$m$个数中$i$的数量

对于一种选择 $s$,答案是

$$\sum_{i=0}^{2^n-1}f_i\cdot g_{i \oplus s}$$

$$\sum_{i \oplus j=s}f_i\cdot g_j$$

使用 FWT 完成这个异或卷积

复杂度 $\mathcal O(nm+n\times 2^n)$


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = read(); !isdigit(c); c = read()) {
if (c == '-') iosig = true;
if (c == -1) return;
}
for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
if (iosig) x = -x;
}

const int N = 22, M = 100005, K = 1<<20;
int n, m, a[M];
ll f[K], g[K];
inline void FWT(ll *f, int g, int len=1<<n){
for(int i=1; i<len; i<<=1)
for(int j=0; j<len; j+=i<<1)
for(int k=j; k<j+i; ++k){
ll x=f[k], y=f[k+i];
f[k]=x+y, f[k+i]=x-y;
}
if(g==-1) for(int i=0; i<len; ++i) f[i]>>=n;
}
int main() {
read(n), read(m);
for(int i=0; i<n; ++i){
char ch;
while(isspace(ch=read()));
for(int j=0; j<m; ++j, ch=read()) a[j]=a[j]<<1|(ch^'0');
}
for(int i=0; i<m; ++i) ++f[a[i]];
for(int i=1; i<1<<n; ++i) g[i]=g[i^(i&-i)]+1;
for(int i=0; i<1<<n; ++i) g[i]=min(g[i], n-g[i]);
FWT(f, 1), FWT(g, 1);
for(int i=0; i<1<<n; ++i) f[i]*=g[i];
FWT(f, -1);
int ans=1e9;
for(int i=0; i<1<<n; ++i) ans=min(ans, (int)f[i]);
return printf("%d", ans), 0;
}