【51Nod】1920 空间统计学 状压DP

【题目】1920 空间统计学
【题意】给定m维空间中的n个点坐标，满足每一维坐标大小都在[0,3]之间，现在对于[0,3*m]的每个数字x统计曼哈顿距离为x的有序点对数。\(n \leq 2*10^5,m \leq 9\)。
【算法】状压DP
m范围很小，考虑设计状压DP的状态，可以想到设到达某个坐标j（将m维坐标压成m位四进制数）步数为k（距离等价于步数）的点数，但是难以转移。考虑按维转移，考虑每一维往外走的情况来转移。
设\(f_{i,j,k}\)表示前i维，到达坐标j，步数为k的点数。转移时枚举第i+1维的坐标l，假设坐标j的第i+1维是x，那么：

$$f(i+1,j+(l-x)*4^i,k+|x-l|)+=f(i,j,k)$$

最后统计答案的时候，对于每个点坐标j将f[m][j][~]累加进答案即可。
复杂度\(O(m*4^m*3m*4)\)。
注意：1.时限比较紧，要用读入优化，枚举步数上限3*i等优化常数。2.空间比较紧，要用滚动数组（好像可以不用？）。

#include
#include
#include
bool isdigit(char c){return c>='0'&&c<='9';}
int read(){
	int s=0,t=1;char c;
	while(!isdigit(c=getchar()))if(c=='-')t=-1;
	do{s=s*10+c-'0';}while(isdigit(c=getchar()));
	return s*t;
}
using namespace std;
const int maxn=270010;
int abs(int x){return x>=0?x:-x;}
int n,m,f[2][maxn][30],b[10],t[maxn];
int main(){
	n=read();m=read();
	b[0]=1;for(int i=1;i<=m;i++)b[i]=b[i-1]*4;
	for(int i=1;i<=n;i++){
		int num=0;
		for(int j=1;j<=m;j++)num=num*4+read();
		f[0][num][0]++;//
		t[i]=num;
	}
	int o=0;
	for(int i=0;i