← 返回题目列表

AtCoder · xmascon22_g

G. 生成器可满足性

中文机器翻译题面 查看原题

配点 : 100 点

对于输入生成以代码或伪代码给出的题目,如果不仔细阅读他人的代码,或者将他人的代码整合到解答中,可能会出现准备团队没有预料的启发式解法被接受的情况,这些通常并不理想,但希望您可以将其理解为“稍微奇特的问题”,予以谅解。

問題文

1 每个输入文件 T 测试用例。每个测试用例中的整数 N, S ,回答以下问题。

整数 A_0, A_1, \ldots, A_{4N-1} 规定如下。用数学公式和 C++ 代码片段表示: 按照此顺序对

  1. 変数 s 该值应乘以 s \gets S 。
  2. i = 0, 1, \ldots, 4 N - 1 , 先作为A_i \gets \lfloor i/4 \rfloor + 1 。
  3. 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 。
  4. 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 定为好整数,就能满足条件。