Loading...

CF662C Binary Table

check评论:0 条 remove_red_eye浏览量:29 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-12-04

链接

好久没做$FWT$了ww

$g_i$表示列状态为$i$时$0/1$个数中的较小值

$f_i$表示状态为$i$的列的数量

$ans=\sum\limits_{i=0}^{2^n} f_i \times g_{i\oplus s}$

$ans=\sum\limits_{s=0}^{2^n}\sum\limits_{i=0}^{2^n} f_i\times g_{i \oplus s}$

$ans_s=\sum\limits_{i\oplus j =s} f_i\times g_j $

显然搞出$f$和$g$后$xor$卷积一下就可以啦

#include <bits/stdc++.h>
using namespace std;
int f[2000010],g[2000010],ans[2000010];
int n,m;
char s[22][100010];
void FWT(int *x,int flag)
{
    for(int mid=1;mid<(1<<n);mid<<=1)
    {
        for(int k=0,r=(mid<<1);k<(1<<n);k+=r)
        {
            for(int i=0;i<mid;i++)
            {
                int dx=x[i+k],dy=x[i+k+mid];
                x[i+k]=(dx+dy),x[i+k+mid]=(dx-dy);
                if(flag==-1)
                {
                    x[i+k]/=2,x[i+k+mid]/=2;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s[i]+1);
    }
    for(int i=1;i<=m;i++)
    {
        int now=0;
        for(int j=1;j<=n;j++)
        {
            if(s[j][i]=='1')
            {
                now|=(1<<(j-1));
            }
        }
        f[now]++;
    }
    for(int i=0;i<(1<<n);i++)
    {
        int qwq=__builtin_popcount(i);
        g[i]=min(qwq,n-qwq);
    }
    FWT(f,1),FWT(g,1);
    for(int i=0;i<(1<<n);i++)
    {
        ans[i]=f[i]*g[i];
    }
    FWT(ans,-1);
    int nans=n*m+1;
    for(int i=0;i<(1<<n);i++)
    {
        nans=min(nans,ans[i]);
    }
    cout<<nans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名