No.2651 [Cherry 6th Tune B] $\mathbb{C}$omplex комбинат
タグ : / 解いたユーザー数 40
作問者 : 👑
Kazun
/ テスター :
👑 
p-adic
問題文
この問題では虚数単位は $\sqrt{-1}$ と書くことにする.
$N$ 個の複素数 $z_1, \dots, z_N$ がある. $i=1,2, \dots, N$ に対して, $z_i$ は整数 $x_i, y_i$ を用いて, $z_i = x_i + y_i \sqrt{-1}$ と表せる. なお, $z_i \neq 0$ である.
$S$ を $$S := \sum_{i=1}^{N-1} \sum_{j=i+1}^N \left|\dfrac{z_i}{z_j} - \dfrac{z_j}{z_i} \right|^2$$ とすると, $S$ は有理数であることが証明できる. $S \pmod{998244353}$ を求めよ.
ただし, 複素数 $w$ に対して, $\left| w \right|$ で $w$ の複素数の意味での絶対値を表す.
$T$ 個のテストケースについて答えよ.
注記
この問題の制約下においては, $S$ に対して, 以下を満たすような整数 $A,B$ が存在する.
- $A$ は $998244353$ の倍数ではない.
- $A \times S = B$.
この $A,B$ に対して, $A \times C \equiv B \pmod{998244353}$ となる $0$ 以上 $998244353$ 未満の整数 $C$ が唯一存在するので, この $C$ を用いて, $S \pmod{998244353}:=C$ とする.
なお, $A \times S =B$ となる $998244353$ の倍数ではない整数 $A$ と整数 $B$ は数多に考えられるが, $C$ は $A,B$ の取り方によらず, $S$ にのみによって決まる.
制約
- $1 \leq T \leq 10^5$.
- 各テストケースにおける制約
- $2 \leq N \leq 3 \times 10^5$.
- $-2 \times 10^4 \leq x_i \leq 2 \times 10^4, - 2 \times 10^4 \leq y_i \leq 2 \times 10^4 \quad (1 \leq i \leq N)$.
- $z_i \neq 0 \quad (1 \leq i \leq N)$
- テストファイルにおける制約
- $T$ 個のテストケースにおける $N$ の総和は $3 \times 10^5$ 以下である.
- 入力は全て整数である.
入力
$T$
$\textrm{Testcase}_1$
$\textrm{Testcase}_2$
$\vdots$
$\textrm{Testcase}_T$
各テストケースは以下の形式である.
$N$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_N$ $y_N$
出力
出力は $T$ 行からなる. 第 $t~(1 \leq t \leq T)$ 行目には, 第 $t$ テストケースに対する解答を出力せよ.
最後に改行を忘れないこと.
サンプル
サンプル1
入力
3 3 1 1 2 0 1 2 2 4 -6 4 -6 5 46 46 12345 6789 -14142 13562 -13579 2468 0 1
出力
149736660 0 106880605
- [第 $1$ テストケース]
$z_1 = 1 + \sqrt{-1}, z_2 = 2, z_3 = 1 + 2 \sqrt{-1}$ である. そして,
$$\left|\dfrac{z_1}{z_2} - \dfrac{z_2}{z_1} \right|^2 = \left|-\dfrac{1}{2} + \dfrac{3}{2} \sqrt{-1} \right|^2 = \dfrac{5}{2}, \quad \left|\dfrac{z_1}{z_3} - \dfrac{z_3}{z_1} \right|^2 = \left|-\dfrac{9}{10} - \dfrac{7}{10} \sqrt{-1} \right|^2 = \dfrac{13}{10}, \quad \left|\dfrac{z_2}{z_3} - \dfrac{z_3}{z_2} \right|^2 = \left|-\dfrac{1}{10} - \dfrac{9}{5} \sqrt{-1} \right|^2 = \dfrac{13}{4}$$ となるので, $S=\dfrac{5}{2}+\dfrac{13}{10}+\dfrac{13}{4}=\dfrac{141}{20}$ となる.
また, $20 \times S = 141$ であり, $20 \times 149736660 \equiv 141 \pmod{998244353}$ であるので, $S \pmod{998244353} = 149736660$ である.
- [第 $2$ テストケース]
$z_1=z_2=4 - 6 \sqrt{-1}$ であるので, $S=0$ となる.
サンプ_2
入力
1 13 1 29 4 17 4 18 10 12 12 19 3 23 10 21 8 29 1 12 10 13 7 10 1 2 9 28
出力
591212021
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。