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$ 的值。 ```cpp #include std::vector Generate(int N, long long S) { long long s = S; std::vector 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 翻译