全国最大机械采购平台/合肥seo推广排名

Description

给出m维平面上的n个点，每个点的每维坐标在[0,3]范围内
对于i=0~3m，求曼哈顿距离为i的点对数量
n<=200000,m<=9

Solution

被鞋垫教做题QwQ我真是太菜了
才不是什么FWT呢
考虑状压Dp，压4进制m位
Fi,j,s表示考虑完前i为，走了j步，到状态为j的点数
然后直接求答案即可
复杂度O(4^(m+1)*3m^2)

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;typedef long long ll;int read() {char ch;for(ch=getchar();ch<'0'||ch>'9';ch=getchar());int x=ch-'0';for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x;
}const int M=(1<<18)+5,N=10;int n,m,a[N],b[M][N],four[N];
ll f[2][M][N*3],Ans[N*3];int Abs(int x) {return x>0?x:-x;}int in(int *a) {int res=0;fo(i,1,m) res=res*4+a[i];return res;
}int main() {n=read();m=read();fo(i,1,n) {fo(j,1,m) a[j]=read(),b[i][j]=a[j];f[0][in(a)][0]++;}fo(i,1,m) a[i]=3;int all=in(a);four[0]=1;fo(i,1,m) four[i]=four[i-1]<<2;int p=0,q=1;fo(i,1,m) {fo(s,0,all) fo(j,0,3*(i-1)) {int now=s/four[m-i]%4;fo(x,0,3) f[q][s-(now-x)*four[m-i]][j+Abs(x-now)]+=f[p][s][j];}swap(p,q);memset(f[q],0,sizeof(f[q]));}fo(i,1,n) {fo(j,1,m) a[j]=b[i][j];int now=in(a);fo(j,0,3*m) Ans[j]+=f[p][now][j];}fo(i,0,3*m) printf("%lld ",Ans[i]);
}