解题报告：CodeForces - 662C:Binary Table FWT(快速沃尔什变换)-程序员宅基地
题意：
给定一个至多20*100000的01矩阵，可以选择任意行或列，选择行或列的01值改变，问经过操作能到最少的含1的数量。
思路：
因为行最大为20，考虑将每一列压缩成一个20位的整数，选择的行也最多只有20，同样压缩到一个20位的整数。
改变行上的01值，对应的操作为异或，那么就能写出对应的卷积式：
根据异或运算的性质，可以交换j,k的位置，得到：
C[k] : 选择操作的行的集合为k的最少含1数量
A[i]： 列上数值为 i 的个数
B[j]： 数 j 的最少含1个数
这就是一个标准的可以用FWT进行加速的卷积运算了
代码：
#include<bits/stdc++.h>
using namespace std;
void FWT(long long a[],int l,int on){
for(int d=1;d<l;d<<=1){
for(int m=d<<1,i=0;i<l;i+=m){
for(int j=0;j<d;j++){
long long x = a[i+j],y=a[i+j+d];
a[i+j]=x+y;
a[i+j+d]=x-y;
if(on<0){
a[i+j]>>=1;
a[i+j+d]>>=1;
}
}
}
}
}
int n,m;
char str[100005];
int A[100005];
long long num[1<<21];
long long B[1<<21];
long long C[1<<21];
int main()
{
scanf("%d%d",&n,&m);
long long ans = n * m;
for(int i=1,x;i<=n;i++){
scanf("%s",str+1);
for(int j=1;j<=m;j++){
x = str[j]-'0';
A[j] = (A[j]<<1) + x ;
}
}for(int i=1;i<=m;i++){
num[A[i]]++;
}int l = (1<<n);
for(int i=0;i<l;i++){
B[i] = B[i>>1] + (i&1);
C[i] = min(B[i],n-B[i]);
}FWT(num,l,1);FWT(C,l,1);
for(int i=0;i<l;i++){
C[i] = C[i] * num[i];
}FWT(C,l,-1);
for(int i=0;i<l;i++){
ans = min(ans,C[i]);
}printf("%I64d\n",ans);
return 0;
}
智能推荐
程序如何运行：编译、链接、装入_浮动目标码模块-程序员宅基地
文章浏览阅读1.9w次，点赞47次，收藏173次。1. 地址相关概念1. 物理地址(physical address) 物理内存，真实存在的插在主板内存槽上的内存条的容量的大小. 内存是由若干个存储单元组成的，每个存储单元有一个编号，这种编号可唯一标识一个存储单元，称为内存地址（或物理地址）。我们可以把内存看成一个从0字节一直到内存最大容量逐字节编号的存储单元数组，即每个存储单元与内存地址的编号相对应。_浮动目标码模块
SpringMVC（四、统一异常处理_spring mvc 统一异常处理-程序员宅基地
文章浏览阅读653次。使用@RestControllerAdvice注解对项目可能产生的异常进行统一处理。_spring mvc 统一异常处理
STM32基础学习_32单片机学习资料-程序员宅基地
文章浏览阅读2.5k次，点赞3次，收藏22次。P3 串口电路一键下载原理分析上拉电路三极管b为基极，c为集电极，e为发射极作开关使用时，NPN型三极管：b接低电平，则电路截止，b接高电平则电路饱和导通；PNP型三极管：b接高电平，则电路截止，b接低电平则电路饱和导通P5 初识STM32PCB打样选择深圳嘉立创公司引脚顺序：从黑点开始逆时针旋转为正方向写好的程序编译之后都是一条条指令，存放在 FLASH中，内核要读取这些指令来执行程序就必须通过 ICode 总线..._32单片机学习资料
RxJava源码分析之subscribeOn和observeOn_subscribeon observeon-程序员宅基地
文章浏览阅读6.1k次，点赞2次，收藏4次。RxJava源码分析之subscribeOn和observeOnRxJava的特色就是可以改变他的任务线程，可以很优雅的在子线程和主线程中切换，而切换用到的两个主要方法是subscribeOn()和observeOn().备注：因本人水平有限，以下分析只代表本人所见，如有不当，请见谅并指出。subscribeOn()和observeOn()的区别subscr_subscribeon observeon
『SQLServer系列教程』——IF/WHILE/CASE逻辑控制语句用法_sqlserver if用法-程序员宅基地
文章浏览阅读1.6k次，点赞4次，收藏19次。读完这篇文章里你能收获到：1 学会SQLServer中IF/WHILE/CASE逻辑控制语句用法，2 提供实际操作的案例SQL脚本_sqlserver if用法
Postman—命令行执行脚本及生成报告（postman+Newman+Jenkins）_postman 命令行-程序员宅基地
文章浏览阅读720次。Postman—命令行执行脚本、生成报告、Jenkins持续集成_postman 命令行
随便推点
Linux内存管理：什么是CMA（contiguous memory allocation）连续内存分配器？可与DMA结合使用_swiotlb-程序员宅基地
文章浏览阅读1.1w次，点赞17次，收藏93次。目录1. 概述1.1.为什么在默认版本中使用它2. 数据结构3. 流程分析3.1 CMA区域创建3.1.1 方式一 根据dts来配置3.1.2 方式二 根据参数或宏配置3.2 CMA添加到Buddy System3.3 CMA分配/释放3.4 DMA使用4.CMA利弊4.1.优点4.2.缺点5.为什么要摆脱CMA5.1.如何摆脱CMA5.1.1.启用连贯池5.1.2. DMA分配技巧5.1.3.离子分配器6.CMA document_swiotlb
腾讯云Windows云服务器配置多用户远程以及配置其他用户远程权限-程序员宅基地
文章浏览阅读1.9k次。基于腾讯云Windows云服务器配置多用户远程一、设置允许多用户远程登录 Windows 云服务器1、点击即可跳转腾讯云部署文档2、可以使用同一个用户名来测试配置成功，用户名和密码均相同测试Windows系统的云服务器默认用户名为Administrator可以使用微软的远程桌面远程一下看是否成功..._腾讯云windows云服务器配置多用户远程
【Unity3D插件】“我敢说，这是你见过最多的插件合集”Unity插件分享不断更新中。。。_unityuiextensions-程序员宅基地
文章浏览阅读4.1w次，点赞57次，收藏374次。推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群：1040082875 大家好，我是佛系工程师☆恬静的小魔龙☆，不定时更新Unity开发技巧，觉得有用记得一键三连哦。一、前言 最近整理了一下文章，发现我分享了很多的插件，但是如果要查找某一款插件，还需要去搜索才能找到，很不方面，就想要将写过的所有的插件分享也好，教程也好，做一个汇总，然后这篇文章还会不断的更新，在有新的插件之后。 熟悉我的人都知道，我对插件是情有独钟，因为好的插件能极大._unityuiextensions
前端HTML——三大元素之块元素 内联块元素 和内联元素_aside是否为块元素?-程序员宅基地
文章浏览阅读686次，点赞5次，收藏3次。块元素div就是一个块元素，所谓的块元素就是会独占一行的元素，无论它的内容有多少都会独占一行p h1 h2…都是块元素div这个标签没有任何语义，就是一个纯粹的块元素并且不会为它里面的元素设置任何的默认样式块元素主要用来对页面进行布局内联元素span就是一个内联元素（行内元素）所谓的行内元素，指的是只占自身大小的元素，不会占用一行常见的内联元素：a img iframe spanspan没有任何的语义，专门用来选中文字，然后为文字设置样式内联元素主要用来用来选中文字，然_aside是否为块元素?
Java IO：在文件上创建文件锁-程序员宅基地
文章浏览阅读196次。为什么80%的码农都做不了架构师？>>> ...
守护进程与后台进程（Python 创建守护进程）-程序员宅基地
文章浏览阅读3k次。文章目录一、守护进程与后台进程1. 守护进程1.1 代码实现为什么要fork两次umask权限掩码进程组会话组2. 后台进程3. 守护进程与后台进程区别4. 使用场景总结二、参考一、守护进程与后台进程1. 守护进程编写守护进程的一般步骤步骤：（1）创建自己成并被init进程接管：在父进程中执行fork并exit退出；（2）创建新进程组和新会话：在子进程中调用setsid函数创建新的会话；（3）修改子进程的工作目录：在子进程中调用chdir函数，让根目录 ”/” 成为子进程的工作目录；（4）修改_守护进程