題目描述

有一個\(n\)行\(m\)列的表格，每個元素都是\(0/1\)，每次操作可以選擇一行或一列，把\(0/1\)翻轉，即把\(0\)換為\(1\)，把\(1\)換為\(0\)。請問經過若干次操作后，表格中最少有多少個\(1\)。

題解

但凡跟狀態轉移扯上一點關系的題目就沒我什么事了……

首先，我們可以枚舉每一行是否反轉，然后每一次就可以\(O(m)\)的計算出答案，然而這樣的復雜度是\(O(2^nm)\)的，會掛

我們設\(a[S]\)表示狀態為\(S\)的列有多少個，\(b[S]\)表示狀態\(S\)中\(0\)和\(1\)的個數中較小的那一個，設當前的行狀態為\(now\)，可以有如下轉移\[ans=\sum_{i=0}^{2^n}a[i]\times b[i⊕now]\]
因為有\(i⊕i⊕now=now\)，所以轉移可以寫成如下形式\[ans[now]=\sum_{i⊕j=now}a[j]*b[j]\]
用\(FWT\)優化即可，復雜度為\(O(2^n\log(2^n))=O(n*2^n)\)

//minamoto #include<bits/stdc++.h> #define R register #define ll long long #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; const int N=(1<<20)+5; char s[N];int sz[N],g[N],n,m,lim;ll A[N],B[N],ans=1e9; void FWT(ll *A,int ty){for(R int mid=1;mid<lim;mid<<=1)for(R int j=0;j<lim;j+=(mid<<1))for(R int k=0;k<mid;++k){ll x=A[j+k],y=A[j+k+mid];A[j+k]=x+y,A[j+k+mid]=x-y;if(ty==-1)A[j+k]/=2,A[j+k+mid]/=2;} } signed main(){ // freopen("testdata.in","r",stdin);scanf("%d%d",&n,&m),lim=1<<n;fp(i,1,n){scanf("%s",s+1);fp(j,1,m)g[j]|=(s[j]-'0')<<(i-1);}fp(i,1,m)++A[g[i]];fp(i,1,lim-1)sz[i]=sz[i>>1]+(i&1);fp(i,0,lim-1)B[i]=min(sz[i],n-sz[i]);FWT(A,1),FWT(B,1);fp(i,0,lim-1)A[i]=A[i]*B[i];FWT(A,-1);fp(i,0,lim-1)cmin(ans,A[i]);printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/bztMinamoto/p/10198577.html

總結

以上是生活随笔為你收集整理的CF662C Binary Table的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。