题目 Idea 来自 call_me_std。
出题人做法不是递归构造,是直接构造。
建立一个模 $p$ 意义下的 $k$ 维空间,这样空间中恰好有 $p^k$ 个点,我们让原图每一个点对应空间中一个点。
枚举一个非零向量 $v$ 和起点 $x$,把 $x, x+v, x+2v,\ldots, x+(p-1)v$ 分为一组即可。
显然两个不同点唯一确定同一组里剩下 $p-2$ 个点。
证明可以考虑在模 $p$ 意义下运算的唯一性($p$ 不为质数时并不能这样构造)。
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int p, k, n = 1;
scanf("%d%d", &p, &k);
puts("YES");
for (int i = 0; i < k; i++) {
n *= p;
}
std::function<int(int, int)> add = [&] (int x, int y) {
int result = 0, power = 1;
for (int i = 0; i < k; i++, x /= p, y /= p, power *= p) {
result = result + (p + x % p + y % p) % p * power;
}
return result;
};
std::vector<std::vector<bool>> visit(n, std::vector<bool>(n));
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) if (!visit[i][j]) {
//找一条还没处理的边(i,j),求出同一组剩下的点
std::vector<int> index(1, i);
int v = add(j, -i);
for (int l = 1; l < p; l++) {
index.push_back(add(index.back(), v));
}
for (auto x : index) {
printf("%d ", x);
for (auto y : index) {
visit[x][y] = true;
}
}
puts("");
}
}
return 0;
}
```