← 返回题目列表

AtCoder · utpc2024_f

F. 傅里叶系数

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

配点 : 100 点

問題文

这个问题是互动问题(这是由你编写的程序与裁判程序通过标准输入输出进行交互的题目形式)。裁判程序的执行最长约为 1.3 秒。

整数 N 被给出。裁判程序私下拥有函数 f(x) \coloneqq \sum_{k=0}^{N-1} A_k \cos{kx} 。这里,通过如下的A_0, \dots, A_{N - 1} 是 您也可以写 0 以上 998244353 的整数。

次对话,输出整数 A_0, \dots, A_{N - 1} 。

  • 你 N 整数集 给出了 (X_1, Y_1), \dots, (X_N, Y_N) 。对于每一组整数 (X_i, Y_i) 是 您也可以写 0 \le X_i \le Y_i < 998244353 和 Y_i \neq 0 。
  • ,裁判程序会返回 N 整数 给出了 Z_1, \dots, Z_N 。每个整数 Z_i 是 您也可以写 Z_i \coloneqq f(\arccos(X_i / Y_i)) \bmod 998244353 被定义。
Z_i 的严格定义在 X_i, Y_i 的约束下,f(\arccos(X_i / Y_i)) 会成为有理数,特别是当用最简分数 P_i / Q_i 表示时,会得到 Q_i \not\equiv 0 \pmod{998244353} 。 此时,作为小于 Z_i ,0 以上 998244353 的整数,并且满足Z_i Q_i \equiv P_i \pmod{998244353} 的整数被定义。值得注意的是,可以证明这样的 Z_i 总是存在且唯一。

制約

  • 所有输入均为整数
  • 1 \leq N \leq 5 \times 10^{5}

入出力

这个问题是一个交互问题(你的程序和判断程序通过标准输入和输出交互的问题)。

首先,N 。

N

然后,请按以下格式将满足条件的 (X_1, Y_1), \dots, (X_N, Y_N) 输出到标准输出。

X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

如果输出是合法的,响应将以以下格式从标准输入提供。

Z_1
Z_2
\vdots
Z_N

如果输出是不合法的,则作为响应 -1 。 对于

-1

-1 被输入时,请立即终止程序。

之后,请按以下格式将答案输出到标准输出。

A_0
A_1
\vdots
A_{N-1}

注意点

  • 每次打印输出时,在末尾添加一个换行符并刷新标准输出。如果不这样做,判断结果将是 TLE 。
  • 如果对话过程中输出错误或程序中途终止,则判断结果不确定。
  • 输出答案后(或者 -1 收到后)请立即正常终止程序。如果不这样做,裁判结果将不确定。
  • 特别要小心,因为额外的换行符也被视为无效的格式化输出。
  • 裁判不是自适应的。也就是说,整数 A_0, \dots, A_{N - 1} 在对话开始时是固定的,在对话过程中不会更改。

入出力例

以下是 N = 2 和 (A_0, A_1) = (3, 2) 的输入/输出示例。

入力 出力 説明
2 N 。 对于
0 1
1 1
满足条件 (X_i, Y_i) 被查询。
3
5
f(\arccos(X_i / Y_i)) 的值将作为响应提供。
3
2
答案为 (A_0, A_1) = (3, 2) 。