CF662C Binary Table （快速沃尔什变换FWT）
2024-10-20 00:35:13
题面
题解
我们会发现，如果单独的一列或一行，它的答案是O1确定的，如果确定了每一行是否变换，那么最后的答案也就简单了许多，
如果确定了行的变换状压下来是x（即x的i位表示第i行是否变换，理解就行），那么每列的状态就要异或x，这没问题吧
接着，其实它的行列是可以交换顺序的，对答案没有影响，状态一定的列的最终贡献都一样，
所以就把状态为 i 的列的数量记为 c[i]，方便计算，
然后，提前预处理出列的状态为 i 时单独考虑的答案 f[i]（即反转或不反转的最小1数量），方便计算
若枚举行的变换x，那么
注意，xor的逆运算是xor！
于是，就转变成了卷积，用FWT就行了，最后枚举x算最小值完事
害怕答案会爆的朋友也可以使用取模，由于最终的答案肯定不会超过1e6，所以你的模数只要超过1e6就没有影响答案。
ＣＯＤＥ
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define MAXN (1<<20|5)
#define LL long long
#define lowbit(x) (-(x) & (x))
#define ENDL putchar('\n')
#define rg register
#pragma GCC optimize(2)
//#pragma G++ optimize(3)
//#define int LL
char char_read_before = 1;
inline int read() {
int f = 1,x = 0;char s = char_read_before;
while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}
while(s >= '0' && s <= '9') {x = x * 10 - '0' + s;s = getchar();}
char_read_before = s;return x * f;
}
inline int readone() {
int x = 0;char s = getchar();
while(s < '0' || s > '9') s = getchar();
char_read_before = 1;return s - '0';
}
int zxy = 1000000007; // 用来膜的
int inv2 = (zxy+1)/2;
inline int qm(LL x,int dalao) {return x >= dalao ? qm(x-dalao,dalao):x;}
int n,m,i,j,s,o,k;
inline void DWTXOR(int *s,int m) {
for(int k = m;k > 1;k >>= 1) {
for(int i = 0;i < m;i += k) {
for(int j = i+(k>>1);j < i+k;j ++) {
int s0 = s[j-(k>>1)],s1 = s[j];
s[j] = qm((s0 +0ll+ zxy - s1) , zxy);
s[j-(k>>1)] = qm((s0 +0ll+ s1) , zxy);
}
}
}
return ;
}
inline void IDWTXOR(int *s,int m) {
for(int k = 2;k <= m;k <<= 1) {
for(int i = 0;i < m;i += k) {
for(int j = i+(k>>1);j < i+k;j ++) {
int s0 = s[j-(k>>1)],s1 = s[j];
s[j-(k>>1)] = qm((s0 +0ll+ s1) , zxy) *1ll* inv2 % zxy;
s[j] = qm((s0 +0ll+ zxy - s1) , zxy) *1ll* inv2 % zxy;
}
}
}
return ;
}
inline void DWTOR(int *s,int m) {
for(int k = m;k > 1;k >>= 1) {
for(int i = 0;i < m;i += k) {
for(int j = i+(k>>1);j < i+k;j ++) {
int s0 = s[j-(k>>1)],s1 = s[j];
s[j] = qm((s0 +0ll+ s1) , zxy);
}
}
}
return ;
}
inline void IDWTOR(int *s,int m) {
for(int k = 2;k <= m;k <<= 1) {
for(int i = 0;i < m;i += k) {
for(int j = i+(k>>1);j < i+k;j ++) {
int s0 = s[j-(k>>1)],s1 = s[j];
s[j] = qm((s1 +0ll+ zxy - s0) , zxy);
}
}
}
return ;
}
inline void DWTAND(int *s,int m) {
for(int k = m;k > 1;k >>= 1) {
for(int i = 0;i < m;i += k) {
for(int j = i+(k>>1);j < i+k;j ++) {
LL s0 = s[j-(k>>1)],s1 = s[j];
s[j-(k>>1)] = qm((s0 +0ll+ s1) , zxy);
}
}
}
return ;
}
inline void IDWTAND(int *s,int m) {
for(int k = 2;k <= m;k <<= 1) {
for(int i = 0;i < m;i += k) {
for(int j = i+(k>>1);j < i+k;j ++) {
int s0 = s[j-(k>>1)],s1 = s[j];
s[j-(k>>1)] = qm((s0 +0ll+ zxy - s1) , zxy);
}
}
}
return ;
}
int A[MAXN],B[MAXN],as[MAXN];
int ct[MAXN],a[MAXN];
int main() {
n = read();m = read();
int M = 1<<n;
for(int i = 1;i < M;i ++) {
ct[i] = ct[i ^ lowbit(i)] + 1;
A[i] = min(ct[i],n - ct[i]);
}
for(int i = 0;i < n;i ++) {
for(int j = 1;j <= m;j ++) {
s = readone();
a[j] |= (s<<i);
}
}
for(int i = 1;i <= m;i ++) B[a[i]] ++;
DWTXOR(A,M);DWTXOR(B,M);
for(int i = 0;i < M;i ++) as[i] = A[i] *1ll* B[i] % zxy;
IDWTXOR(as,M);
int ans = 0x7f7f7f7f;
for(int i = 0;i < M;i ++) ans = min(ans,as[i]);
printf("%d\n",ans);
return 0;
} 最新文章
- 【转】java.util.ResourceBundle使用详解
- 2016"百度之星" - 初赛（Astar Round2A）Gym Class(拓扑排序)
- Socket通信实例（C#）
- ip
- Python学习总结19：类（二）
- python中使用zip函数出现<zip object at 0x02A9E418>
- C++ STL 简单记录
- Django写的投票系统2（转）
- 文档发布工具mkdocs
- 2>&1 什么意思
- 20165309 《网络对抗技术》实验一：PC平台逆向破解
- Hadoop 单表关联
- MySQL 5.7忘记root密码如何修改?
- 使用PHPExcel将数据导出至Excel
- haar的简单应用(2)
- mac homebrew
- 算法第四版-文字版-下载地址-Robert Sedgewick
- python3中的编解码
- 命令行下IIS的配置脚本Adsutil.vbs
- tomcat上部署CGI