配点 : 100 点
对于输入生成以代码或伪代码给出的题目,如果不仔细阅读他人的代码,或者将他人的代码整合到解答中,可能会出现准备团队没有预料的启发式解法被接受的情况,这些通常并不理想,但希望您可以将其理解为“稍微奇特的问题”,予以谅解。
問題文
1 每个输入文件 T 测试用例。每个测试用例中的整数 N, S ,回答以下问题。
整数 A_0, A_1, \ldots, A_{4N-1} 规定如下。用数学公式和 C++ 代码片段表示: 按照此顺序对
- 変数 s 该值应乘以 s \gets S 。
- i = 0, 1, \ldots, 4 N - 1 , 先作为A_i \gets \lfloor i/4 \rfloor + 1 。
- i = 0, 1, \ldots, 4 N - 1 , 先作为s \gets (s \times 2022) \bmod 998244353 , 再从s \not\equiv 0 \pmod{2} 如果 A_i \gets -A_i 。
- i = 0, 1, \ldots, 4 N - 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;
}
各 j = 1, 2, \ldots, N 反对 +j 和 按字典顺序比较 -j 中恰好选择一个称为“好整数”的方法 在 2^N 种方法中,判断是否存在满足以下 N 个条件的情况,如果存在,请求出这样的方法的 1 种。
- A_0, A_1, A_2, A_3 至少 1 个是良好整数。
- A_4, A_5, A_6, A_7 至少 1 个是良好整数。
- \cdots
- A_{4N-4}, A_{4N-3}, A_{4N-2}, A_{4N-1} 至少 1 个是良好整数。
制約
- 1 \le T \le 10.
- 1 \le N \le 10^5.
- 0 \le S < 998244353.
入力
标准输入 1 排队测试用例数 给出了 T 。之后,T 测试用例均按以下格式给出。
N S
出力
关于每个测试用例,如果能够满足以下条件, 1 请按行输出。
可以选择良好整数的方式有 1 种,长度如下 N 的字符串:每个 j = 1, 2, \ldots, N , 定义
- +j 是良好的整数,
当无法满足j 第一个字符是
+。 - -j 是良好的整数,
当无法满足j 第一个字符是
-。
条件时,
在第0 。
入力例 1
2 3 1 4 20221224
出力例 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 定为好整数,就能满足条件。