[xsy3132]数表

佚名 6年前 (2019-05-04) 随笔 838人围观抢沙发百度已收录

题意：一个$n\times m$的数表，数值$\in[0,4)$，你可以任意次选择一行或一列$+1,\text{mod }4$，要最小化所有数的和

因为$n\leq10$，所以数表可以看成$m$个$n$位$4$进制数$a_{1\cdots m}$，以下使用不进位加法

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

定义$f(x)=\min\limits_{i=0}^3\left(x+(i\cdots i)_4\right)$，如果确定了行的方案$s$，答案就是$\sum\limits_if(a_i+s)$

记$c_x$为$x$在$a_{1\cdots m}$中的出现次数，$\text{ans}(s)=\sum\limits_xc_xf(x+s)=\sum\limits_{a+b=s}c_{-a}f(b)$，是一个高维循环卷积

高维卷积需要用到高维FFT，根据wiki，只需在每一维分别dft即可，时间复杂度$O(n4^n)$

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=998244353,inf=2147483647;
int mul(int a,int b){return(ll)a*b%mod;}
int ad(int a,int b){return(a+=b)>=mod?a-mod:a;}
int pow(int a,int b){
	int s=1;
	while(b){
		if(b&1)s=mul(s,a);
		a=mul(a,a);
		b>>=1;
	}
	return s;
}
int*w[5],iN;
void pre(){
	int i,j,t;
	for(i=2;i<=4;i<<=1){
		w[i]=new int[i+1];
		t=pow(3,(mod-1)/i);
		w[i][0]=1;
		for(j=1;j<=i;j++)w[i][j]=mul(w[i][j-1],t);
	}
	iN=pow(4,mod-2);
}
void dft4(int*a,int sh,int on){
	#define a(i) a[(i)<<sh]
	const int N=4;
	int i,j,k,t;
	swap(a(1),a(2));
	for(i=2;i<=N;i<<=1){
		for(j=0;j<N;j+=i){
			for(k=0;k<i>>1;k++){
				t=mul(a(i/2+j+k),w[i][on==1?k:i-k]);
				a(i/2+j+k)=ad(a(j+k),mod-t);
				a(j+k)=ad(a(j+k),t);
			}
		}
	}
	if(on==-1){
		for(i=0;i<N;i++)a(i)=mul(a(i),iN);
	}
	#undef a
}
int n,N;
void dft(int*a,int on){
	int i,j;
	for(j=0;j<n;j++){
		for(i=0;i<N;i++){
			if(!(i>>j*2&3))dft4(a+i,j*2,on);
		}
	}
}
int a[10010];
int c[1048576],f[1048576];
int t[4];
int main(){
	int m,i,j,x,res;
	scanf("%d%d",&n,&m);
	N=1<<n*2;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			scanf("%d",&x);
			a[j]=a[j]<<2|x;
		}
	}
	for(i=1;i<=m;i++)c[a[i]]++;
	reverse(c,c+N);
	for(i=0;i<N;i++){
		t[0]=t[1]=t[2]=t[3]=0;
		for(j=0;j<n;j++)t[i>>j*2&3]++;
		f[i]=min(min(t[1]+2*t[2]+3*t[3],t[0]+2*t[1]+3*t[2]),min(t[3]+2*t[0]+3*t[1],t[2]+2*t[3]+3*t[0]));
	}
	pre();
	dft(c,1);
	dft(f,1);
	for(i=0;i<N;i++)c[i]=mul(c[i],f[i]);
	dft(c,-1);
	res=inf;
	for(i=0;i<N;i++)res=min(res,c[i]);
	printf("%d",res);
}