Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

CF662C Binary Table

Posted on Edited on

FMT不会，贺的。

Solution

首先我们观察数据范围，发现n和m的范围严重不平衡，得出结论需要枚举每一行是否翻转,提前将每一列状压后我们可以再对每一列贪心，这样就得到了暴力的$O(m2^n)$。

这个东西发现我们是动不了的，考虑转化这个式子，首先将每一列转化成1的个数最少的状态，枚举每一列显然是不可做的，为了将这个m替换掉，我们将每一行的是否翻转状压成一个二进制数,定义有g(x)个列的状态为F(x)，最后答案就是：$\min(\sum S\sum x [Y=x \ xor \ S]F(Y)*g(x))$，F可以预处理 ，这样枚举的就变成S和x了，复杂度就变为$O(2^{2n})$，但依然无法通过此题。

再次考虑转化，大佬们都已经看出其中的蹊跷了，这就是FMT模板，套上去就完事了。

Code

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res), putchar(' ');
}
const int N = 21, M = 1e5 + 5, mod = 998244353;
int n, m;
int a[N][M], b[N];
int f[1 << N], h[1 << N];
inline int popcount(int x)
{
	int cnt = 0;
	for(int i = x; i;i -= i & (-i)) cnt ++;
	return cnt;
}
inline void FWT_XOR(int x[], int op)
{
	if(op == -1) op = 499122177;
	for(int i = 0;i < n;i ++)
		for(int j = 0, a, b;j < (1 << n);j ++)
		{
			if(j >> i & 1) continue;
			a = x[j], b = x[j | (1 << i)];
			x[j] = 1ll * (a + b) % mod * op % mod;
			x[j | (1 << i)] = 1ll * (a - b + mod) % mod * op % mod;
 		}
}
int ans = 0x3f3f3f3f;
int main()
{
	read(n, m);
	for(int i = 1;i <= n;i ++)
		for(int j = 1;j <= m;j ++)
		{
			char c = getchar();
			while(c != '0' && c != '1') c = getchar();
			a[i][j] = c - '0';
		}
	for(int i = 1;i <= m;i ++)
		for(int j = 1;j <= n;j ++)
			b[i] = (b[i] << 1) + a[j][i];
	for(int i = 1;i <= m;i ++) f[b[i]] ++;
	for(int i = 0;i < 1 << n;i ++) h[i] = popcount(i);
	for(int i = 0;i < 1 << n;i ++) h[i] = min(h[i], n - h[i]);
	FWT_XOR(f, 1), FWT_XOR(h, 1);
	for(int i = 0;i < (1 << n);i ++) f[i] = 1ll * f[i] * h[i] % mod;
	FWT_XOR(f, -1);
	for(int i = 0;i < (1 << n);i ++) ans = min(ans, f[i]);
	write(ans);
	return 0;
}