自动搬运

查看原文

来自洛谷，原作者为

	UnyieldingTrilobite 直到世界 只剩下闪烁的黑白

搬运于2025-08-24 23:15:25，当前版本为作者最后更新于2025-05-08 16:04:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先来考虑这样一个问题：我们现在手上有数 $a_1,a_2,a_3,a_4,\cdots,a_{t-1}$ 各两个，另有 $a_t$ 四个，我们要如何构造一个比较好的操作次数来完成题目的要求？

记 $x=a_t$。我们先把三个 $x$ 放着不动，一个 $x$ 依次和 $a_1,a_2,\cdots,a_{t-1}$ 操作。此时我们剩下的数形如：$x,x,a_1x,a_1a_2x,\cdots,(\prod_{j=1}^ia_j)x,\cdots,(\prod_{i=1}^ta_i),(\prod_{i=1}^ta_i),a_1,a_2,\cdots,a_t$。这一步一共 $t-1$ 次操作。

记 $y=\prod_{i=1}^ta_i$。我们令 $y$ 依次和 $a_t,a_{t-1},\cdots,a_1$ 操作。此时我们剩下的数形如：$x,x,a_1x,a_1a_2x,\cdots,(\prod_{i=1}^{t-2}a_i)x,y,xy,a_{t-1}a_ty,\cdots,(\prod_{j=i}^ta_j)y,\cdots,(\prod_{i=1}^ta_i)y,(\prod_{i=1}^ta_i)y$。其中最后两项实际上就是 $y^2$。这一步一共 $t$ 次操作。

$\forall 1\le i\le t$，将 $(\prod_{j=1}^{i-1}a_j)x$ 与 $(\prod_{j=i}^ta_j)y$ 操作，得到两个 $xy^2$。这一步一共 $t$ 次操作。

此时场上不为 $xy^2$ 的数还有 $x$ 和 $y^2$ 各一个，操作一次即可。这一步一共 $1$ 次操作。

以上加起来一共 $3t$ 次操作。

回到原题，$n$ 为奇数时显然无解（因为 $n>1$），$n\le 2$ 显然特判，接下来考虑 $n$ 是 $\ge 4$ 的偶数，记为 $2t+2$（$t\ge 1$）。

对于 $1\le i\le t+1$，我们对 $a_{2i-1}$ 和 $a_{2i}$ 操作，这一步一共 $t+1$ 次操作。接下来我们对 $a_{n-3}$ 和 $a_{n-1}$ 操作，$a_{n-2}$ 和 $a_n$ 操作，这一步一共 $2$ 次操作。加起来一共 $t+3$ 次操作，此时我们把问题化归为了一开始解决的那个。于是一共 $4t+3$ 次操作，我们在 $2n-1$ 步内对原问题完成了解决。

代码对着这个东西实现就可以了。

#include <bits/stdc++.h>
using namespace std;
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T, n;
  for (cin >> T; T; --T) {
    if (cin >> n, n & 1) {
      cout << "0\n";
      continue;
    }
    if (cout << 1 << '\n', n == 2) {
      cout << "1 1 2\n";
      continue;
    }
    cout << (n << 1) - 1 << '\n';
    auto op = [](int x, int y) { cout << x << ' ' << y << '\n'; };
    int t = (n >> 1) - 1;
    for (int i = 1; i <= t + 1; ++i) op((i << 1) - 1, i << 1);
    op(n - 3, n - 1), op(n - 2, n);
    for (int i = 1; i <= t - 1; ++i) op(n - 1, (i << 1) - 1);
    for (int i = t; i; --i) op(n - 1, i << 1);
    for (int i = 1; i < t; ++i) op((i << 1) - 1, (i + 1) << 1);
    op(2, n - 3), op(n - 1, n);
  }
  return cout << flush, 0;
}