解题报告：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;
}
智能推荐
Android如何实现获取手机CPU的温度?-程序员宅基地
文章浏览阅读7.8k次，点赞3次，收藏10次。Android如何实现获取手机CPU的温度?在做项目过程中，有时需要获取手机CPU的温度。目前市面上常见的CPU主要有两种：MTK（联发科）、Qualcomm（高通）。当然还有我们华为的海思麒麟CPU，以及三星的CPU。后两种CPU在本篇文章中就不做展开，有兴趣的同学，可以自行去研究研究。通过研究发现，CPU的信息基本都是在/sys/class/thermal/目录下，通过adb shell...
C/C++ 静态代码检查工具cppCheck_cppcheck自定义规则-程序员宅基地
文章浏览阅读850次。Cppcheck是一个用于C/C++代码的静态分析工具，它可以帮助开发者检测代码中的错误；Cppcheck可以检测出许多类型的错误，包括语法错误、未使用的函数、内存泄漏、未初始化的变量等；Cppcheck还支持用户自定义规则，这使得开发者可以根据自己的需求定制Cppcheck的行为；使用--suppress如果你想要忽略某些警告，可以在命令行中使用 --suppress 选项。_cppcheck自定义规则
Centos7 青龙面板_centos7安装青龙面板-程序员宅基地
文章浏览阅读3.1w次，点赞37次，收藏315次。Centos7 青龙面板 狗东豆 欢太（2022.4.24更新）一、前期准备 。二、安装宝塔面板。三、安装青龙面板，以及拉各种库。四、安装XDD-PLUS。（机器人）五、其他批注。一、前期准备 。1.购买云服务器 点击购买操作系统选择CentOS 7的最后一个版本就可以。2，下载远程连接工具 FinalShell，[用这个比较方便，选择你电脑合适的电系统本下载就可以] 点击下载3，更改实例密码4，FinalShell 远程连接（1）点击箭头所指白色文件夹，选择SSH连接（Linux）_centos7安装青龙面板
USB学习(1)：USB基础之接口类型、协议标准、引脚分布、架构、时序和数据格式_从零开始学usb(一、基础知识1)-程序员宅基地
文章浏览阅读2.7k次，点赞3次，收藏23次。连接计算机外围设备最简单的方法是通过USB(通用串行总线USB是即插即用接口，可以将扫描仪、打印机、数码相机、闪存驱动器等计算机外围设备连接到计算机上。本篇文章就来介绍一下USB的一些基础知识。_从零开始学usb(一、基础知识1)
rhcsa命令大全_rhcsa 命令大全-程序员宅基地
文章浏览阅读322次。重启： reboot , shutdown -r now关机： shutdown -h now , poweroff查看当前Linux的发行版信息： cat /etc/redhat-release查看内核版本： uname -r输出和更改日期时间： date（软件、系统时间）更改日期的格式 月 日 时 分 年 秒date -s 20200528 //日期为2020年5月28日，时间为00:00:00date -s 01:01:01 //设置具体时间，不会更改其他_rhcsa 命令大全
java下拉框怎么做_java下拉框怎么做？-程序员宅基地
文章浏览阅读2.3k次。有朋友在做Java相关开发时因为一些问题可愁坏了。比如这个问题，java下拉框怎么做？本篇文章将和大家讲述如何用Java实现下拉框，感兴趣的朋友了解一下。引用的包有：java.awt是一个软件包，包含用于创建用户界面和绘制图形图像的所有分类。在AWT术语中，诸如按钮或滚动条之类的用户界面对象称为组件。javax.swing 最常用的pachage，包含了各种swing组件的类javax.swing..._java jpanel下拉框
随便推点
已解决Error:java: Compilation failed: internal java compiler error-程序员宅基地
文章浏览阅读6.8w次。Error:java: Compilation failed: internal java compiler error是编译器在编译Java代码时遇到的内部错误。_java: compilation failed: internal java compiler error
宁波市第32届中小学生程序设计竞赛（初中组） 母鸡下蛋_问题 c: 母鸡下蛋-程序员宅基地
文章浏览阅读1.6k次。问题 C: 母鸡下蛋鸡国中的母鸡最擅长下蛋了，MGMG 是鸡国中一只以下蛋产量高而闻名全鸡国的母鸡。 鸡国专供下蛋的 n 个鸡窝呈一字排列在鸡国的“下蛋中心”，从左到右依次编号为 1 到n。每个鸡窝都有一个最大可下蛋的量，其中第 i 个鸡窝的最大可下蛋量为 ci 。有时候由于MGMG 产量实在太大而无法在一个鸡窝中下完所有的蛋，不得不转移到隔壁的鸡窝继续下蛋，如果隔壁的鸡窝还是不能让它_问题 c: 母鸡下蛋
nodejs+vue+elementui咖啡商城销售系统qi99g_vue node商城-程序员宅基地
文章浏览阅读873次，点赞15次，收藏18次。通过咖啡在线销售这个平台，可以使用户足不出户就可以了解现今的咖啡信息，为用户提供了极大的方便，咖啡在线销售的主要功能包含：店铺信息管理、注册用户管理、商品信息管理等模块。前台子系统为用户提供注册、登陆的功能，以及浏览咖啡，购买咖啡，提交订单后采用模拟的金额支付，实现咖啡的购买流程。后台子系统供网站内部管理人员使用，可以咖啡修改和删除、注册用户管理、店铺信息管理等功能，对用户的订单进行管理。另外一部分是网站的后台管理部分，这部分包括：对普通用户的账号进行删除、更改、查询管理，咖啡的管理、订单的管理等。_vue node商城
Lingo与最短路问题_lingo最短路问题-程序员宅基地
文章浏览阅读1.2w次，点赞4次，收藏82次。Lingo与最短路问题 代码如下：!最短路问题;model:data: n=10;enddatasets: cities/1..n/: F; !10个城市; roads(cities,cities)/ 1,2 1,3 2,4 2,5 2,6 3,4 3,5 3,6 4,7 4,8 5,7 5,8 5..._lingo最短路问题
C++进程间通信的多种方式及实现-程序员宅基地
文章浏览阅读6k次，点赞7次，收藏66次。多进程通信_c++进程间通信
Hue的安装与部署-程序员宅基地
文章浏览阅读95次。Hue的安装与部署hadoophueHue 简介Hue是一个开源的Apache Hadoop UI系统，最早是由Cloudera Desktop演化而来，由Cloudera贡献给开源社区，它是基于Python Web框架Django实现的。通过使用Hue我们可以在浏览器端的Web控制台上与Hadoop集群进行交互来分析处理数据，例如操作HDFS上的数据，运行MapReduce Job等等。很..._server_conn_timeout