5271 题解

2019-03-23 22:28:29


题目 Idea 来自 call_me_std。

出题人做法不是递归构造,是直接构造。

建立一个模 $p$ 意义下的 $k$ 维空间,这样空间中恰好有 $p^k$ 个点,我们让原图每一个点对应空间中一个点。

枚举一个非零向量 $v$ 和起点 $x$ ,把 $x, x+v, x+2v,\ldots, x+(p-1)v$ 分为一组即可。

显然两个不同点唯一确定同一组里剩下 $p-2$ 个点。

证明可以考虑在模 $p$ 意义下运算的唯一性( $p$ 不为质数时并不能这样构造)。

#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;
}