【前言】
这是一道非常精彩的好题，虽然被凯文大佬嘲讽是“弱智题”，但是仍然教会了我一些东西。
【题意】
给定一个六边形网格，按如下方法编号：
给定 \(n\) 个点，求有多少种非空集合 \(S\)，满足集合内每两个点的距离（指每次可以跨过网格的任意一条边，多少步才能到达）都 \(\le D\)。
\(n \le 400, D \le 10^{10}, x_i,y_i \le 10^9\)
【分析】
首先先想到去推距离的式子。然后推出来是：对于 \((x,y)\)，其到 \((0,0)\) 的距离就是：\(\max\{|x|,|y|,|x-y|\}\)。
推出来这一步之后，我不知道应该要干什么，而这是思路的第一个转折点：考虑到转换坐标。从上个式子发现：如果我们把 \((x,y)\) 转化为 \((x,y,x-y)\)，那么两点的距离会转化为三维切比雪夫距离。
转坐标的方法很常见，例如你想把一个坐标系旋转 \(45\) 度，使得一个斜正方形被转化为一个正的正方形，就是把 \((x,y)\) 转化为 \((x+y)/2, (x-y)/2\)，而曼哈顿转切比雪夫恰恰是这么做的。
然后呢？转化为计算有多少个集合里的点可以放在一个 \(D\times D\times D\) 的窗格里？乍一看又不会做了。没事，我们考虑一维的怎么做。这是一个降维的思路，先把问题弱化一下，然后再考虑推广，这时会更有思路。
一维怎么做啊，想到了可以枚举最左边那个元素 \(x\)，然后对于 \([x+1,x+D]\) 内的元素求子集数即可。这样不会重复不会漏算。
推广到二维？枚举卡在的左下角呗。这时候出现一个问题了：像这样的集合，并不存在一个刚好位于左下角的点，那应该怎么统计到它？我们可以 \(O(n^2)\) 枚举 \(x\) 和 \(y\) 分别的下界，这样就可以卡住了。
这时候我们发现，我们要分开来讨论：用一个位于左下角的边界来卡这个正方形，还是用一个左边一个下边的边界来卡这个正方形。这两个情况都要考虑，并且为了不重不漏，计算第二种情况的时候不能选到左下角的点。
一个矩形内的点的个数可以通过二维前缀和来求出。总时间复杂度就是 \(O(n^2)\) （按照凯文说的基数排序？）或者带一个 \(\log\)（因为离散化之后要二分）。
然后就是推广到三维。这时候我们已经有底了：时间复杂度会是接近 \(O(n^3 \log n)\) 的。然后需要使用三维前缀和，还需要分类讨论很多东西，考虑很多式子怎么求。一想就很难写啊！
但是，做题的重点在于想 + 调，写不算什么。还是能写的。不过在写之前我们一定要理清楚应该怎么写。
【实现】
考虑三维前缀和怎么做。二位前缀和是基于容斥，三维的也是。容斥怎么写？正负号看 \(-1\) 的个数嘛！不用思考就可以写出这样的式子，经过简单验证是正确的：
s[x][y][z]=a[x][y][z]+s[x-1][y][z]+s[x][y-1][z]+s[x][y][z-1]-s[x-1][y-1][z]-s[x-1][y][z-1]-s[x][y-1][z-1]+s[x-1][y-1][z-1];
然后是枚举 \(x,y,z\) 下界并找到正方体的位置。自然是离散化，枚举的下界个数为 \(O(n^3)\)。\((x+D,y+D,z+D)\) 的位置在离散化数组里不一定找得到，我们需要找到离散化数组中第一个 $\le $ 它的位置。我采用了这样的写法：（一定要注意特判 lower_bound 到了 end 的时候！）
int a=mx(disx[x]+d);if(a>xc||disx[a]!=disx[x]+d)a--;
int b=my(disy[y]+d);if(b>yc||disy[b]!=disy[y]+d)b--;
int c=mz(disz[z]+d);if(c>zc||disz[c]!=disz[z]+d)c--;
为了简单起见，考虑 \((x,y,z)=(0,0,0)\)。然后考虑应该怎么记录。有了二维的启发，想到肯定要记录原点上/某个轴上/某个面上/普通（也就是分三维坐标有哪些为 \(0\)）点的个数，然后才能算。
不妨设 \(pure_{0 \sim 7}\) 分别表示：
\[others \\ x=0\\ y=0\\ z=0\\ x=y=0\\ x=z=0\\ y=z=0\\ x=y=z=0 \]且每一行没有提到的坐标均 \(\neq 0\) 的点的个数。
然后是魔鬼推式子环节。在这个迷宫中，一定要时刻手握火把，不能瞎推，要有条理。
我们要计算以 \((0,0,0)\) 为顶点，\(D\) 为边长的正方体中，所有的非空集合 \(T\)，使得不存在更大的顶点能够包围住 \(T\)。
以下是我做这个题的时候的糟糕的思路：
如果存在一个原点上的点，那么其他点选什么都可以。如果存在一个形如 \(x=0\) 的点，并且存在一个形如 \(y=z=0\) 的点，那么也可以。如果存在 \(x=0,y=0,z=0\) 三个，那么也可以。
（一通乱写，发现错得离谱。虽然更离谱的是还过样例了，并且样例一直都过着，无论式子多离谱）
WA 了啊，诶，原来 \(x=y=0\) 和 \(x=z=0\) 这样的都有也可以啊，哎呀，漏了一种情况。
又 WA，怎么回事？（一通调）诶，是不是这里会算重啊？那应该在 \(x=y=0\) 和 \(x=z=0\) 的时候不让再出现 \(y=0\) 才行。改改代码。
还是 WA。...。WA 了若干发之后，手造一组数据和一个暴力开始跑。发现错了。
哪里错了？找不到啊？（盯着代码看）（盯着数据看）（检查前面已经写对的东西）
发现好像有一组 \(pure_{0 \sim 7}\) 的取值我算出来答案好像不一样。诶，是式子写错啦！删删改改，终于过了手造数据了。交上去果然过了。
以上做题过程用时一天。
这怎么行啊！不能这样做题啊。
经过深刻的反思，我发现了：
- 首先，一个问题就是没有手造一个比较强的样例自己测测。下次一定要造。
- 然后我的思考方式完全是乱的啊！一团浆糊！应该怎么思考？我觉得应该这样：
【以下为我觉得对的思考过程】
考虑一个集合 \(S\) 具有哪个性质的时候，被哪一步筛出。记上述 \(pure_i\) 记录的点为 \(i\) 类点。
-
当 \(S\) 中存在一个在原点上的点（\(7\) 类点）时，用一个步骤筛出，这个步骤是：原点上的点必选一个，其他的在 \(0 \sim 6\) 类中任选。
-
当 \(S\) 中没有原点的时候，如果三个轴上都存在点（也就是存在 \(4,5,6\) 类点）那么这三个轴上每一个都必须选一个点，其他的在 \(0 \sim 3\) 类中任选。
-
当 \(S\) 中没有原点，并且只有两个轴存在点，那么有三种情况，每种情况分别选择两个轴，在这两个轴上每一个都必须选一个点，其他的在 \(0 \sim 3\) 类中任选。
-
当 \(S\) 中没有原点，并且只有一个轴存在点，那么有三种情况，每种情况分别选择一个轴，并且必须还存在一个 \(1 \sim 3\) 中某一类（比如这个轴是 \(x=y=0\) 的 \(4\) 号点，那么还需要存在 \(z=0\) 的 \(3\) 号点）。这两类点中每一个都必须选一个点，其他的在 \(0 \sim 3\) 类中除了被选出来的点之外其他的点中任选。
-
当 \(S\) 中没有原点，并且没有轴存在点，那么 \(1 \sim 3\) 中每一类点都必须存在一个，其他的在 \(0\) 类点中任选。
这样可以不重不漏地计算，并且没有其他的构造点集的方法。
这样之后，问题就转化为了：若干个集合 \(S_1,S_2,...\) 中每个集合都必须选择至少一个点，剩余的点在集合 \(T\) 中任选，得到的集合方案数？
别急。都到最后了，虽然简单，但还是不要乱推，保持思路的清晰。
清楚地推五秒，发现这个问题的结论是：
\[(\prod \limits_i(2^{|S_i|} - 1)) \times 2^{T} \]至此，问题完美解决了。
【代码】
By Zeardoe
这次我觉得是写的比较清楚的，前几次看的代码很有作用。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
const int mod = 998244353;
int disx[410], disy[410], disz[410];
int xc,yc,zc;
struct dot {
int x,y,z;
dot() {}
dot(int _x,int _y,int _z):x(_x),y(_y),z(_z){
disx[++xc]=x;disy[++yc]=y;disz[++zc]=z;
}
}p[410];
int a[410][410][410], s[410][410][410];
int mx(int x){return lower_bound(disx+1,disx+xc+1,x)-disx;}
int my(int y){return lower_bound(disy+1,disy+yc+1,y)-disy;}
int mz(int z){return lower_bound(disz+1,disz+zc+1,z)-disz;}
int cnt[8],pure[8],jc[410],ny[410],pow2[410];
int qpow(int x,int k){int ans=1;while(k){if(k&1)ans=ans*x%mod;x=x*x%mod;k>>=1;}return ans;}
int calc(int x,int y,int z,int a,int b,int c){return s[a][b][c]-s[x-1][b][c]-s[a][y-1][c]-s[a][b][z-1]+s[x-1][y-1][c]+s[x-1][b][z-1]+s[a][y-1][z-1]-s[x-1][y-1][z-1];}
void prework(){jc[0]=ny[0]=pow2[0]=1;f(i,1,400){jc[i]=jc[i-1]*i%mod;ny[i]=qpow(jc[i],mod-2);pow2[i]=pow2[i-1]*2%mod;}}
int bino(int n, int m) {if(n==0)return 0;if(m==1)return pow2[n] - 1;return 114514;}
signed main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//time_t start = clock();
//think twice,code once.
//think once,debug forever.
int n, d; cin >> n >> d;
prework();
f(i, 1, n) { int x,y;cin>>x>>y; p[i]=dot(x,y,x-y); }
sort(disx+1,disx+xc+1);sort(disy+1,disy+yc+1);sort(disz+1,disz+zc+1);
xc=unique(disx+1,disx+xc+1)-disx-1;yc=unique(disy+1,disy+yc+1)-disy-1;zc=unique(disz+1,disz+zc+1)-disz-1;
f(i, 1, n) { a[mx(p[i].x)][my(p[i].y)][mz(p[i].z)]++; }
f(x,1,xc)f(y,1,yc)f(z,1,zc) s[x][y][z]=a[x][y][z]+s[x-1][y][z]+s[x][y-1][z]+s[x][y][z-1]-s[x-1][y-1][z]-s[x-1][y][z-1]-s[x][y-1][z-1]+s[x-1][y-1][z-1];
int ans=0;
f(x,1,xc)f(y,1,yc)f(z,1,zc) {
f(i,0,7)cnt[i]=0;
int a=mx(disx[x]+d);if(a>xc||disx[a]!=disx[x]+d)a--;
int b=my(disy[y]+d);if(b>yc||disy[b]!=disy[y]+d)b--;
int c=mz(disz[z]+d);if(c>zc||disz[c]!=disz[z]+d)c--;
cnt[0]=calc(x,y,z,a,b,c);cnt[1]=calc(x,y,z,x,b,c);cnt[2]=calc(x,y,z,a,y,c);cnt[3]=calc(x,y,z,a,b,z);
cnt[4]=calc(x,y,z,x,y,c);cnt[5]=calc(x,y,z,x,b,z);cnt[6]=calc(x,y,z,a,y,z);cnt[7]=calc(x,y,z,x,y,z);
pure[0]=cnt[0]-cnt[1]-cnt[2]-cnt[3]+cnt[4]+cnt[5]+cnt[6]-cnt[7];
pure[1]=cnt[1]-cnt[4]-cnt[5]+cnt[7];pure[2]=cnt[2]-cnt[4]-cnt[6]+cnt[7];pure[3]=cnt[3]-cnt[5]-cnt[6]+cnt[7];
pure[4]=cnt[4]-cnt[7];pure[5]=cnt[5]-cnt[7];pure[6]=cnt[6]-cnt[7];pure[7]=cnt[7];
//三个点都在面上
ans=(ans+bino(pure[1],1)*bino(pure[2],1)%mod*bino(pure[3],1)%mod*pow2[pure[0]]%mod)%mod;
//一个点在面上，只有一个点在轴上
ans=(ans+bino(pure[4],1)*bino(pure[3],1)%mod*pow2[pure[0]+pure[2]+pure[1]]%mod)%mod;
ans=(ans+bino(pure[5],1)*bino(pure[2],1)%mod*pow2[pure[0]+pure[3]+pure[1]]%mod)%mod;
ans=(ans+bino(pure[6],1)*bino(pure[1],1)%mod*pow2[pure[0]+pure[3]+pure[2]]%mod)%mod;
//只有两个点在轴上
ans=(ans+bino(pure[4],1)*bino(pure[5],1)%mod*pow2[pure[0]+pure[1]+pure[2]+pure[3]]%mod)%mod;
ans=(ans+bino(pure[5],1)*bino(pure[6],1)%mod*pow2[pure[0]+pure[1]+pure[2]+pure[3]]%mod)%mod;
ans=(ans+bino(pure[6],1)*bino(pure[4],1)%mod*pow2[pure[0]+pure[1]+pure[2]+pure[3]]%mod)%mod;
//三个点都在轴上
ans=(ans+bino(pure[4],1)*bino(pure[5],1)%mod*bino(pure[6],1)%mod*pow2[pure[0]+pure[1]+pure[2]+pure[3]]%mod)%mod;
//一个点在原点
ans=(ans+bino(pure[7],1)*pow2[cnt[0]-pure[7]]%mod)%mod;
}
cout << ans << endl;
//time_t finish = clock();
//cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
return 0;
}
【后记】
红题是弱智题？对于水平高的同学来说确实是这样。但是要怎样成为水平高的同学？总结复盘非常重要。