题意
(n imes m) 的表格，一次操作可以将一行或一列在模 (4) 意义下加 (1)，问任意次操作后表格内数之和的最小值。(nleq 10,mleq 10^4)
题解
行上的操作确定后，每一列都容易确定最优解。
记 (c(i)) 为列上状态为 (i) 的列的个数，(f(i)) 为当一列为 (i) 时，做列操作后的最小和。二者做减法卷积便能得到每种行操作下的最优答案。
(4) 进制的高维循环卷积类似于异或卷积，但在循环内要做长为 (4) DFT（暴力即可）
减法卷积在翻转系数时怎么做都能过，但大多数写法得到的结果顺序其实是乱的。
#include<bits/stdc++.h>
using namespace std;
const int N=21;
int f[1<<N],c[1<<N],rt=86583718,mod=998244353,inv4=(mod*3ll+1)/4;
int a[11][10001];
int p[4],q[4];
void dft(int tp){
int r=1;
for(int i=0;i<4;i++){
q[i]=0;
for(int j=3;j>=0;j--)
q[i]=(q[i]*1ll*r+p[j])%mod;
r=r*1ll*rt%mod;
}
if(tp==-1){
swap(q[1],q[3]);
for(int i=0;i<4;i++)q[i]=q[i]*1ll*inv4%mod;
}
}
void fwt(int *a,int lim,int tp){
for(int i=1;i<lim;i<<=2){
for(int j=0;j<lim;j+=i<<2){
for(int k=0;k<i;k++){
// cerr<<"| "<<j+k<<" "<<i<<endl;
for(int l=0;l<4;l++)p[l]=a[i*l+j+k];
dft(tp);
for(int l=0;l<4;l++)a[i*l+j+k]=q[l];
}
}
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%d",a[i]+j);
for(int i=0;i<m;i++){
int s=0;
for(int j=0;j<n;j++)
s=(s<<2)|((4-a[j][i])&3);
c[s]++;
// if(s)c[(1<<(n*2))-s]++;
// else c[0]++;
}
for(int i=0;i<(1<<n*2);i++){
int mn=0x7f7f7f7f;
for(int j=0;j<4;j++){
int s=0;
for(int k=0;k<n;k++)
s+=((i>>(k*2))+j)&3;
mn=min(s,mn);
}
f[i]=mn;
}
// for(int i=0;i<1<<(n*2);i++)cerr<<"! "<<c[i];cerr<<endl;
fwt(f,1<<(n*2),1);
fwt(c,1<<(n*2),1);
// for(int i=0;i<1<<(n*2);i++)cerr<<"! "<<c[i];cerr<<endl;
for(int i=0;i<1<<(n*2);i++)f[i]=f[i]*1ll*c[i]%mod;
fwt(f,1<<(n*2),-1);
int ans=0x7f7f7f7f;
for(int i=0;i<1<<(n*2);i++)ans=min(ans,f[i]);
cout<<ans;
}