AT_utpc2024_f Fourier Coefficients

本题为**交互题**（你的程序与评测程序通过标准输入输出进行交互）。评测程序的运行最多需要 $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$ 是满足 $Z_i Q_i \equiv P_i \pmod{998244353}$ 的 $[0, 998244353)$ 内的唯一整数。可以证明，这样的 $Z_i$ 必然存在且唯一。

本题为交互题（你的程序与评测程序通过标准输入输出进行交互）。 首先，从标准输入读取 $N$。 > $N$ 接下来，你需要输出满足条件的 $(X_1, Y_1), \dots, (X_N, Y_N)$，每两个数字之间以空格分隔，所有数值按 $X_1~Y_1~X_2~Y_2~\cdots~X_N~Y_N$ 的顺序输出，最后换行并刷新缓冲区。 > $X_1$ $Y_1$ $X_2$ $Y_2$ $\cdots$ $X_N$ $Y_N$ 如输出合法，评测机会回复 $N$ 个整数 $Z_1, \dots, Z_N$，每个数字之间以空格分隔，表示 $f(\arccos(X_i / Y_i))$ 模 $998244353$ 的值。 > $Z_1~Z_2~\cdots~Z_N$ 如输出不合法，则输入会返回一行 `-1`。 ``` -1 ``` 如果收到 `-1`，请立即退出程序。 之后，请输出你的答案，格式如下： > $A_0~A_1~\cdots~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)$ # 输入格式 详见题面交互过程。 # 输出格式 详见题面交互过程。 # 提示 - 输入均为整数。 - $1 \leq N \leq 5 \times 10^{5}$。 由 ChatGPT 5 翻译