QOJ #8726. [APIO2024] 魔术表演 题解

Description

Alice 和 Bob 是著名的魔术师。Catherine 是一位富豪，她非常喜欢观看 Alice 和 Bob 的魔术。某一天，Catherine 决定向 Alice 和 Bob 发出挑战：只要他们能成功表演如下的魔术，Catherine 就将向他们提供巨额奖金！这个魔术的表演过程如下：

• 步骤 $1$：Bob 进⼊⼀个密室中，在魔术的全程中，他只能与 Catherine 交流。接下来，Alice 告诉 Catherine ⼀个在 $2$ 到 $5000$ 之间的整数 $n$。
• 步骤 $2$：Catherine 告诉 Alice ⼀个在 $1$ 到 $10^{18}$ 之间的整数 $X$。
• 步骤 $3$：Alice 生成⼀个具有 $n$ 个节点的树，并告诉 Catherine。
• 步骤 $4$：Catherine 删除树中的⼀些边（至多 $\left\lfloor\dfrac{n-2}{2}\right\rfloor$ 条），并将剩余的边告诉 Bob。
• 步骤 $5$：Bob 根据 Catherine 给出的信息，猜出 Catherine 告诉 Alice 的数是多少。

然⽽，Alice 和 Bob 被这个魔术难倒了，于是他们不得不寻求你的帮助。请你写一段程序，实现 Alice 和 Bob 的策略，以帮助他们赢得 Catherine 的挑战。

Solution

注意到利用树的形态+编号很难刻画这个数，因为删掉一半的边后整棵树会变得非常不一样。

考虑利用数论去确定这个数。具体的，对于一个数 $v(2\leq v\leq n)$，让 $X\bmod (v-1)+1$ 和 $v$ 连边，这样交互库删掉一半的边后剩下的边也能通过 CRT 非常宽松地得到 $X$。

Code

Alice

#include "Alice.h"
#include <bits/stdc++.h>

std::vector<std::pair<int, int>> Alice() {
  int n = 5000;
  long long x = setN(n);
  std::vector<std::pair<int, int>> ed;
  for (int i = 2; i <= n; ++i) ed.emplace_back(x % (i - 1) + 1, i);
  return ed;  
}

Bob

#include "Bob.h"
#include <bits/stdc++.h>

using i128 = __int128_t;
using pii = std::pair<i128, i128>;

pii merge(pii a, pii b) {
  if (a.second > b.second) std::swap(a, b);
  i128 lcm = a.second / std::__gcd(a.second, b.second) * b.second;
  for (int i = 0; i < a.second; ++i)
    if ((b.first + b.second * i) % a.second == a.first)
      return {b.first + b.second * i, lcm};
}

long long Bob(std::vector<std::pair<int, int>> V) {
  pii now = {0, 1};
  for (auto [u, v] : V) {
    if (u > v) std::swap(u, v);
    now = merge(now, {u - 1, v - 1});
    if (now.second > (i128)1000000000000000000) return (long long)now.first;
  }
}