技术标签： FWT
交的时候 C F CF CF评测鸡咕咕咕了，等了一个中午
由于行很少
考虑一个显然的想法是暴力枚举每行是否翻转
对于每一列就可以贪心做了
O ( 2 20 m ) O(2^{20}m) O(220m)要 T T T
考虑说把每一列看做一个二进制数
行的翻转情况就也是一个二进制数了
设 a [ i ] a[i] a[i]表示二进制数为 i i i的个数， b [ i ] b[i] b[i]为二进制数为 i i i的最小答案(就是翻不翻转取 min \min min)
那么考虑行的翻转情况为 i i i的答案 a n s i = ∑ j ⨁ k = i a j b k ans_i=\sum_{j\bigoplus k=i}a_jb_k ansi=∑j⨁k=iajbk
F w t Fwt Fwt搞一下就完了
#include<bits/stdc++.h>
using namespace std;
#define gc getchar
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define re register
#define pb push_back
#define cs const
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define poly vector<int>
#define bg begin
cs int mod=998244353,G=3;
inline int add(int a,int b){
return (a+=b)>=mod?a-mod:a;}
inline void Add(int &a,int b){
(a+=b)>=mod?(a-=mod):0;}
inline int dec(int a,int b){
return (a-=b)<0?a+mod:a;}
inline void Dec(int &a,int b){
(a-=b)<0?(a+=mod):0;}
inline int mul(int a,int b){
return 1ll*a*b>=mod?1ll*a*b%mod:a*b;}
inline void Mul(int &a,int b){
a=mul(a,b);}
inline int ksm(int a,int b,int res=1){
for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));return res;
}
inline void chemx(ll &a,ll b){
a<b?a=b:0;}
inline void chemn(ll &a,ll b){
a>b?a=b:0;}
cs int N=21,M=(1<<N)|5;
ll A[M],B[M];
int n,m,sta;
char s[N][100005];
inline void Fwt(ll *f,int lim,int kd){
ll a0,a1;
for(int mid=1;mid<lim;mid<<=1)
for(int i=0;i<lim;i+=(mid<<1))
for(int j=0;j<mid;j++)
a0=f[i+j],a1=f[i+j+mid],f[i+j]=a0+a1,f[i+j+mid]=a0-a1;
if(kd==-1)for(int i=0;i<lim;i++)f[i]/=lim;
}
int main(){
n=read(),m=read(),sta=1<<n;
for(int i=0;i<n;i++)
scanf("%s",s[i]+1);
for(int i=1;i<=m;i++){
int res=0;
for(int j=0;j<n;j++)
if(s[j][i]=='1')res+=1<<j;
A[res]++;
}
for(int i=0;i<sta;i++)B[i]=B[i>>1]+(i&1);
for(int i=0;i<sta;i++)chemn(B[i],n-B[i]);
Fwt(A,sta,1),Fwt(B,sta,1);
for(int i=0;i<sta;i++)A[i]*=B[i];
Fwt(A,sta,-1);
ll res=1e18;
for(int i=0;i<sta;i++)chemn(res,A[i]);
cout<<res;
}
文章浏览阅读82次。Description给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。实现 NumArray 类：NumArray(int[] nums) 使用数组 nums 初始化对象int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], … , nums[j])）示例：输入：["NumArray",
文章浏览阅读1.3k次。1 效果图 加载数据时 加载数据完成时 加载数据异常时 2 实现说明 加载前：界面显示异步加载控件，隐藏数据显示控件，加载异常控件 加载成功：根据加载的数据，初始化数据显示控件 加载失败：显示加载异常的控
文章浏览阅读329次。这是涛哥给你推荐的第20篇好文来源：Python全家桶 | 作者：PayneLi最近在Github发现一个基于google浏览器的爬虫项目，此项目是由美国大神2018年开..._google_images_download多于100
文章浏览阅读2w次，点赞2次，收藏15次。AJAX中有检查状态码的，xmlHttp.onreadystatechange=handleStateChange; function handleStateChange() { if(xmlHttp.readyState==4) { if(xmlHttp.status==200) { parseResults(); //解析返回值 } } } r_if(xmlhttp.status==200)
文章浏览阅读3.2k次。今天开始学习慕课网的“去哪网”app开发，之前用学了一段时间对vue还是没有深刻理解透，先在开始要从新开始学习vue，今天学的第一堂课是vue 中v-model、v-for的简单例子，以前改变dom中的数据是操作dom来改变dom中的文本,vue提供的改变数据来改变dom中的内容，这样很大程度上提高了性能，组件中方法中的this是当前组件，可以改变当前组件中的data()方法中的数据，进而改变do..._components中的this指向
文章浏览阅读6.1k次。#include //包含头文件，一般情况不需要改动，头文件包含特殊功能寄存器的定义#define DataPort P0 //定义数据端口 程序中遇到DataPort 则用P0 替换#define KeyPort P1sbit LATCH1=P2^2;//定义锁存使能端口 段锁存sbit LATCH2=P2^3;// 位锁存bit Ke
文章浏览阅读1.2k次。1.现象update regrex set regrex='[^(a-zA-Z0-9\u4e00-\u9fa5)]' where id=1执行完之后，对应的字符串中没有了反斜杠\执行后 反斜杠被mysql转义没了2.原因mysql执行会对内容进行转义，\是特殊对转义字符，转义后消失了，如需要保存反斜杠\ 需要对反斜杠进行转义3.解决方案转义字符特殊处理，再加一个反..._qsql exec 反斜杠消失
文章浏览阅读10w+次，点赞25次，收藏143次。使用Redis的 SETNX 命令可以实现分布式锁，下文介绍其实现方法。SETNX命令命令格式 SETNX key value将 key 的值设为 value，当且仅当 key 不存在 若给定的 key 已经存在，则 SETNX 不做任何动作。 SETNX 是SET if Not eXists的简写。返回值返回整数，具体为 - 1，当 key 的值被设置 - 0，当 key 的值没被设
文章浏览阅读654次。注意事项只能用32bit的版本,64bit版本由于没有对应的libsmi,所以是不支持这个功能的.Wireshark设置正常安装wireshark版本, 2012-2-1本人采用的是稳定的1.6.5版本.安装完成后,打开"Edit"->"Preference"对话框, 点击左侧的"Name Resolution",然后将右侧的"Enable OID resol..._wireshark4 设置mib
文章浏览阅读1.3k次。这里可能存在一个先后的问题：1.先要在Window/show/other中打开Android相关视图，如file Explorer2.然后在启动Android模拟器成功启动。这时会看到android相关视图中出现信息。如果仍然看不到信息。可尝试重启Eclipse，或者更新ADT插件。本人的问题，是重启Eclipse就好了。今天又出现了
文章浏览阅读1.8k次。前言本文的文字及图片来源于网络,仅供学习、交流使用,不具有任何商业用途,如有问题请及时联系我们以作处理。PS：如有需要Python学习资料的小伙伴可以点击下方链接自行获取Python免费学习资料、代码以及交流解答点击即可加入预测是一件复杂的事情，在这方面做得好的企业会在同行业中出类拔萃。时间序列预测的需求不仅存在于各类业务场景当中，而且通常需要对未来几年甚至几分钟之后的时间序列进行预测。如果你正要着手进行时间序列预测，那么本文将带你快速掌握一些必不可少的概念。目录什么是时间序列？ _python rolling mean
文章浏览阅读3.8k次。u3d中有一个碰撞器这么个组件。我个人认为它是u3d中物理触发这块的最根本的一个东西，非常的重要。下面我来说它里面Is Trigger。1、勾选它的 Is Trigger。它就可以穿插到其它的碰撞器中，这是它相当于一个触发器。相关事件在OnTriggerEnter 、OnMouseEnter 、OnTriggerExit 响应。1、不勾选它的Is Trigger这时的它才是一个