F - Fourier Coefficients Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MiB

配点 : 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_iZ_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}

注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が 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) を出力します。