自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 22:33:38，当前版本为作者最后更新于2021-09-12 13:48:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Analysis

考虑数列是乱序的，询问从哪个数开始都是一样的，因此我们不妨考虑询问 $A_1$ 和 $A_2$ 在模意义下的值，并不妨设 $A_1 < A_2$。

从第三个数开始，依次询问每个数和 $A_1$、$A_2$ 的大小关系，则与 $A_1$、$A_2$ 的大小关系不同的位置就是大于 $A_1$ 且小于 $A_2$ 的个数，不妨记为 $k’$，又 $k = k' + 1$，则公差 $d$ 满足如下关系：$A_2 \equiv A_1 + kd(\bmod p)$，即 $kd + pt = A_2 - A_1$，其中 $k$ 和 $p$ 已知。显然 $k$ 和 $p$ 互质，使用 exgcd 解这个方程即可。

查询次数为 $2 + 2\times(n - 1) + 1 = 2n - 1$ 次。最后加上的 $1$ 是查询 $A_1$ 和 $A_2$ 的大小关系。

使用 exgcd 解上述方程的方法是：先解出 $kd' + pt' = 1$ 的解，然后令 $d = d' \times (A_2 - A_1)$、$t = t' \times (A_2 - A_1)$ 即可。

Code

#include <iostream>
#include <algorithm>

const int maxn = 1000005;
const int p = 1000000007;

typedef long long int ll;

int n, q, x, y, z;
int a[2][maxn];

void exgcd(ll a, ll b, ll &xx, ll &yy) {
  if (b == 0) {
    yy = 0; xx = 1;
    return;
  }
  exgcd(b, a % b, yy, xx);
  yy -= xx * (a / b);
}

int main() {
  std::cin >> n >> q;
  for (int i = 3; i <= n; ++i) {
    std::cout << "> 1 " << i << std::endl;
    std::cin >> a[0][i];
    std::cout << "> 2 " << i << std::endl;
    std::cin >> a[1][i];
  }
  int cnt = 0;
  for (int i = 1; i <= n; ++i) if (a[0][i] != a[1][i]) ++cnt;
  std::cout << "? 1" << std::endl;
  std::cin >> x;
  std::cout << "? 2" << std::endl;
  std::cin >> y;
  std::cout << "> 1 2" << std::endl;
  std::cin >> z;
  if (z == 1) std::swap(x, y);
  if (x > y) y += p;
  ll d, t;
  exgcd(cnt + 1, p, d, t);
  d = (d % p + p) % p;
  std::cout << "! " << (d * (y - x) % p) << std::endl;
}