「51nod 1920」空间统计学

发表于

有个 mm 维的空间，并且每一维的坐标 xx 都满足 x∈[0,3]x\in [0,3] 并且 xx 为整数。

这个空间有 nn 个部落，每个部落都坐落在这片空间中的一个点上，可以用坐标 (x1,x2,⋯,xm)(x_1,x_2,\cdots ,x_m) 来表示。

有些部落可能在在同一个点上面。

定义两个点的距离为它们的曼哈顿距离，即每一维坐标差的绝对值的和。

比如对于点 (x1,x2,⋯,xm)(x_1,x_2,\cdots ,x_m) 和 (y1,y2,⋯,ym)(y_1,y_2,\cdots ,y_m) ，它们之间的距离为 ∑i=1m∣xi−yi∣\sum _{i=1}^{m}|x_i-y_i| 。

现在对 [0,3m][0,3m] 之间的每一个数字 xx ，统计有多少对部落之间的距离为 xx。

注意，一对部落是有序的，即部落 (a,b)(a,b) 和部落 (b,a)(b,a) 为不同的两对。

Constraints

n≤200000n\leq 200000 ， m≤9m\leq 9

Solution

观察数据范围可得 mm 和坐标范围都很小，考虑状压 dp 。

令 f(i,j,k)f(i,j,k) 表示当前已经考虑到第 ii 维，到达 jj 这个状态（将坐标压成四进制），当前距离为 kk 的方案数。

转移时枚举上一维的状态和距离以及当前维的坐标，直接转移即可。

利用滚动数组节省空间，时间复杂度 O(12⋅m2⋅4m)O(12\cdot m^2 \cdot 4^m) 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=2e5+5;
const int M=262144+5;
int n,m,x; 
int bit[10],a[N],f[2][M][28];
LL ans;
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int ab(int x){return x>=0?x:-x;}
int main()
{
	n=read();m=read();
	bit[0]=1;
	for(int i=1;i<=m;i++)bit[i]=bit[i-1]*4;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<m;j++)
			x=read(),a[i]+=bit[j]*x;
		f[0][a[i]][0]++;
	}
	int last=0,cur=1;
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<bit[m];j++)
			for(int k=0;k<=3*i;k++)
				f[cur][j][k]=0;
		for(int j=0;j<bit[m];j++)
		{
			x=j/bit[i]%4;
			for(int l=0;l<=3*m;l++)
			{
				if(!f[last][j][l])continue;
				for(int k=0;k<=3;k++)
					f[cur][j+(k-x)*bit[i]][l+ab(k-x)]+=f[last][j][l];
			}
		}
		last=cur;cur=1-cur;
	}
	for(int i=0;i<=3*m;i++)
	{
		ans=0;
		for(int j=1;j<=n;j++)ans+=f[m&1][a[j]][i];
		printf("%lld ",ans);
	}
	return 0;
}