AT_xmascon22_g.Generator SAT

给定一个输入文件，每个文件包含 $T$ 组测试用例。每组测试用例给定整数 $N, S$，请你回答以下问题：

定义整数序列 $A_0, A_1, \ldots, A_{4N-1}$，按照如下方式生成。数式和 C++ 伪代码如下所示：

1. 令变量 $s \gets S$。
2. 对于 $i = 0, 1, \ldots, 4N - 1$，依次令 $A_i \gets \lfloor i/4 \rfloor + 1$。
3. 对于 $i = 0, 1, \ldots, 4N-1$，依次令 $s \gets (s \times 2022) \bmod 998244353$，如果 $s \not\equiv 0 \pmod{2}$，则令 $A_i \gets -A_i$。
4. 对于 $i = 0, 1, \ldots, 4N-1$，依次令 $s \gets (s \times 2022) \bmod 998244353$，然后交换 $A_{s \bmod (i+1)}$ 和 $A_i$ 的值。

#include <vector>
std::vector<int> Generate(int N, long long S) {
  long long s = S;
  std::vector<int> A(4 * N);
  for (int i = 0; i < 4 * N; ++i) {
    A[i] = i / 4 + 1;
  }
  for (int i = 0; i < 4 * N; ++i) {
    s = (s * 2022) % 998244353;
    if (s % 2 != 0) {
      A[i] = -A[i];
    }
  }
  for (int i = 0; i < 4 * N; ++i) {
    s = (s * 2022) % 998244353;
    int j = s % (i + 1);
    int t = A[j];
    A[j] = A[i];
    A[i] = t;
  }
  return A;
}

在下面 $N$ 个条件中，判断是否存在一种从 $2^N$ 种方案中选取 $N$ 个“好的整数”的方式，使得以下每个条件都成立。如果存在这样的方式，请输出其中一组方案：

• 对于每组 $A_{4j}, A_{4j+1}, A_{4j+2}, A_{4j+3}$（$j = 0, 1, \ldots, N-1$），其中至少有一个是“好的整数”。

这里，“好的整数”的选法指：对于每个 $j = 1, 2, \ldots, N$，要么选择 $+j$ 是好整数，要么 $-j$ 是好整数（但不能同时选择），总共有 $2^N$ 种选法。

请判断是否存在满足上述条件的选法。如果存在，请输出其中一组方案。

输入的第一行包含一个整数 $T$，表示测试用例的组数。接下来有 $T$ 组测试用例，每组测试用例如下格式：

$N\ S$

对于每组测试用例，输出一行：

若存在满足所有条件的方案，输出一个长度为 $N$ 的字符串，第 $j$ 位为 '+' 表示 $+j$ 是好整数，为 '-' 表示 $-j$ 是好整数。

如果不存在满足条件的方案，输出 0。

样例解释 1

对于第 $1$ 组测试用例：

• $(A_0, A_1, A_2, A_3) = (-3, -3, -2, +3)$
• $(A_4, A_5, A_6, A_7) = (+2, +1, -1, +3)$
• $(A_8, A_9, A_{10}, A_{11}) = (+2, +1, -2, +1)$

例如，若 $+1, +2, -3$ 被选为好整数，即对应选择 ++-，则所有条件都能满足。

对于第 $2$ 组测试用例：

• $(A_0, A_1, A_2, A_3) = (+3, -2, +2, -3)$
• $(A_4, A_5, A_6, A_7) = (+4, +1, +3, -1)$
• $(A_8, A_9, A_{10}, A_{11}) = (+4, +2, +1, +4)$
• $(A_{12}, A_{13}, A_{14}, A_{15}) = (-1, -2, -3, -4)$

例如，若 $+1, -2, -3, +4$ 被选为好整数，即选择 +--+，则所有条件都能满足。

数据范围

• $1 \le T \le 10$。
• $1 \le N \le 10^5$。
• $0 \le S < 998244353$。

由 ChatGPT 5 翻译