[CodeForces 663E] - Binary Table(FWT)
2024-09-04 03:59:19
题目
分析
本蒟蒻就不赘述了,就是一个看不出来的异或卷积
精髓在于
mask对sta的影响,显然操作后的结果为mask ^ sta
AC code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;//必须用long long,过程中可能炸int
const int MAXN = 1<<20;
const LL INF = 1e18;
const int MAXM = 1e5 + 1;
int n, m, num[MAXM];
LL A[MAXN], B[MAXN];
char str[20][MAXM];
inline int calc(int s)
{
int ret = 0;
while(s) ++ret, s -= s&(-s);
return min(n - ret, ret);
}
inline void FWT(LL arr[], const int &len, const int &flg)
{
register LL x, y;
for(register int i = 2; i <= len; i<<=1)
for(register int j = 0; j < len; j += i)
for(register int k = j; k < j + i/2; ++k)
{
x = arr[k], y = arr[k + i/2];
if(~flg) arr[k] = x + y, arr[k + i/2] = x - y;
else arr[k] = (x + y) / 2, arr[k + i/2] = (x - y) / 2;
}
}
int main ()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i)
scanf("%s", str[i]);
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
num[i] |= (str[j][i] - '0') << j;
++A[num[i]];
}
for(int i = 0; i < (1<<n); ++i)
B[i] = calc(i);
FWT(A, 1<<n, 1);
FWT(B, 1<<n, 1);
for(int i = 0; i < (1<<n); ++i)
A[i] *= B[i];
FWT(A, 1<<n, -1);
LL Ans = INF;
for(int i = 0; i < (1<<n); ++i)
Ans = min(Ans, A[i]);
printf("%I64d\n", Ans);
}
最新文章
- xml 方式更新和获取 配置文件 appSettings 节点 解决办法
- android studio 换护眼的颜色步骤
- Altium Desiner 警告 adding hidden net
- base64 json
- ios(苹果公司的移动操作系统)
- UNIX标准化及实现之功能测试宏
- 腾讯CDC谈扁平化设计
- python -序列化
- vs2013安装visual assist和viemu之后提示功能等无效解决
- FreeBSD 系统的配置.
- Maven的继承以及import作用域
- ASP.NET 发送邮件 SMTP
- openModelica调试
- Logcat多tag过滤
- Dapper,大规模分布式系统的跟踪系统
- ajax return true/false无效原因
- NGS检测SNP
- 头文件dirent.h
- 通过WireShark抓取iOS联网数据实例分析
- UVA 257 Palinwords(hash)题解
热门文章
- Django框架之第八篇(模型层补充)--数据库的查询与优化:only/defer,select_related与prefetch_related,事务
- SQL Server日志处理及安全访问
- 【Linux】Ubuntu替换阿里源
- Gulp 给所有静态文件引用加版本号
- C# vb .net实现圆角矩形特效滤镜
- vue页面跳转拦截器
- 两种方法实现在HTML页面加载完毕后运行JS
- ES6 新增集合----- Set 和Map
- Vue+SpringBoot后端接收包含单属性和List数组的json对象
- day 03 作业 预科