[CF 662C] Binary Table

Posted on | Edited on | In , | Views:

题目链接

CF 662C

做法

听说是一道tourist在考场上都没切的题，不过是真的想不到啊。。。

暴力还是比较好想的，我们枚举翻转哪些行，在队每一列贪心就行了。
先预处理$g(i)$表示状态$i$的答案
显然$g(i)=Min(popcount(i),n-popcount(i))$
复杂度$O(2^n*m)$
发现暴力的瓶颈在于每次枚举状态之后都要$O(m)$枚举一遍。
考虑能不能一起计算。
用$f(i)$表示矩阵初始状态时，状态为$i$的列有多少个。
用$F(i)$表示行翻转状态为i的答案。
那么有

由于$s\oplus i\oplus i=s$

就得到了一个标准的$FWT$卷积形式，用异或卷积卷一下就ok了。
复杂度$O(2^n*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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
using namespace std;
int n,m,lim,invL,ans;
int g[1<<20],popc[1<<20],f[1<<20],a[25][N];
const int P=998244353;
char c[N]; 
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
int ksm(int a,int b){
    int ret=1;
    for (;b;b>>=1,a=1ll*a*a%P) if (b&1) ret=1ll*ret*a%P;
    return ret;
}
inline int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b);
}
inline void FWT(int *f,int g){
    for (int i=1;i<lim;i<<=1){
        for (int j=0;j<lim;j+=(i<<1)){
            for (int k=j;k<i+j;k++){
                int tt=f[k+i];
                f[k+i]=Inc(f[k],P-tt);
                f[k]=Inc(f[k],tt);
            }
        }
    }
    if (g==-1){
        for (int i=0;i<lim;i++) f[i]=1ll*f[i]*invL%P;
    }
}
int main(){
    read(n),read(m);
    ans=n*m;
    lim=1<<n;
    invL=ksm(lim,P-2);
    for (int i=1;i<=n;i++){
        scanf("%s",c+1);
        for (int j=1;j<=m;j++) a[i][j]=c[j]-'0';
    } 
    for (int i=0;i<lim;i++){
        popc[i]=popc[i>>1]+(i&1);
        g[i]=min(popc[i],n-popc[i]);
    }
    for (int i=1;i<=m;i++){
        int tt=0;
        for (int j=1;j<=n;j++){
            tt+=a[j][i]*(1<<j-1);
        }
        f[tt]++;
    }
    FWT(f,1),FWT(g,1);
    for (int i=0;i<lim;i++) f[i]=1ll*f[i]*g[i]%P;
    FWT(f,-1);
    for (int i=0;i<lim;i++){
        ans=min(ans,f[i]);
    }
    printf("%d",ans);
    return 0;
}