题解 CF662C 【Binary Table】
Fading
·
·
题解
这里好像讲得不太清楚，为什么就变成卷积了呢？
我们观察n\leq20,而m达到了惊人的100000!!!
所以我们考虑枚举反转了多少行。
设X表示翻转了哪些行(X是一个整数，表示压缩后的状态)
对于任意一列，设第i列的状态为S_i
比如有一列为
0
1
1
1
这一列的状态就是(1110)_2=(14)_{10}
我们枚举这一列变成了什么东西
设第i列经过翻转变成了状态Y_i
显然有Y_i=S_i\ \texttt{xor}\ X
然后我们发现，对于一个相同的X，最优答案是惟一的，而且X最多只有2^{20}=1048576个，这是可以接受的。
所以我们枚举X。
我们发现，由于每一列可以自由翻转，所以根据贪心原理，我们对于每一个列预先翻转到最少个1为止，设列状态为i时经过翻转这个二进制数最少有F_i个1
比如n=3,F_3,(3)_{10}=(011)_2,翻转后为(100)_2
∴F_3=1
然后我们想方设法凑出F_i
此时答案就是
\sum_{i=1}^mF_{X\ \texttt{xor}\ S_i}
这样复杂度是O(2^nm)的，炸的很惨
我们考虑枚举Y_i=S_i\ \texttt{xor}\ X
此时答案为
\sum_{i=1}^m\sum_{Y=0}^{2^n}[Y==S_i\ \texttt{xor}\ X]F_Y
两个\sum了有什么用呢？
考虑丢掉前面的\sum,设所有列中有Q_i列状态为i
所以前面的枚举就废了
\Leftrightarrow\sum_{S=0}^{2^n}\sum_{Y=0}^{2^n}[Y==S\ \texttt{xor}\ X]F_Y\times Q_S
这样枚举每一个S就可以了。不需要枚举[1,m]了
不过好像还是多了一个\sum，复杂度变成O(2^{2n})了,还是凉凉
怎么办呢？
把式子变一下
\Leftrightarrow\sum_{S=0}^{2^n}\sum_{Y=0}^{2^n}[Y\ \texttt{xor}\ S==S\ \texttt{xor}\ X\ \texttt{xor}\ S]F_Y\times Q_S
\Leftrightarrow\sum_{S=0}^{2^n}\sum_{Y=0}^{2^n}[Y\ \texttt{xor}\ S==X]F_Y\times Q_S
等等，这不就变成FWT模板了吗？？？
如果你还没发现，继续变：
\Leftrightarrow\sum_{Y\ \texttt{xor}\ S=X}F_Y\times Q_S
发现设Ans[X]=\sum_{Y\ \texttt{xor}\ S=X}F_Y\times Q_S
所以套一下模板就好啦！
复杂度优化为了完美的$O(n2^n),n=20\ $轻松解决
简单清爽的代码
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();};
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-48;ch=getchar();};
return x*f;
}
ll n,m,g[21][100201],Q[1400021],F[1400022],S[1400201];
inline void FWTxor(ll *a,int id,int lim){
for (int len=1;len<lim;len<<=1){
for (int i=0;i<lim;i+=len<<1){
ll *a1=a+i,*a2=a1+len;
for (int j=0;j<len;j++){
ll x=a1[j],y=a2[j];
a1[j]=(x+y)/(id==1?1:2);
a2[j]=(x-y)/(id==1?1:2);
}
}
}
}
inline int getch(){//读入单个数字
char s=getchar();
while (!isdigit(s)) s=getchar();
return s-'0';
}
int main(){
n=read(),m=read();
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
g[i][j]=getch();
}
}
for (int i=1;i<=m;i++){
for (int j=1;j<=n;j++){
S[i]|=(1<<j-1)*g[j][i];//预处理S、
}
}
for (int i=0;i<=(1<<n);i++){
Q[i]=Q[i>>1]+(i&1);
}
for (int i=0;i<=(1<<n);i++){
Q[i]=min(Q[i],n-Q[i]);//预处理Q
}
for (int i=1;i<=m;i++){
F[S[i]]++;//预处理F
}
FWTxor(F,1,1<<n);FWTxor(Q,1,1<<n);
for (int i=0;i<(1<<n);i++) F[i]*=Q[i];//FWT优化
FWTxor(F,-1,1<<n);
ll x=999999999;
for (int i=0;i<(1<<n);i++) x=min(F[i],x);
cout<<x<<endl;
}
```
~~突然想安利一下我那完美的$FWT$板子~~