問題一覧 > 通常問題

No.2651 [Cherry 6th Tune B] $\mathbb{C}$omplex комбинат

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 43
作問者 : 👑 Kazun / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10045 / 自分の提出
問題文最終更新日: 2024-02-23 23:57:20
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 418 (Re: start!) (順位表) の他の問題:

Problem Statement

In this problem, the imaginary unit is written as $\sqrt{-1}$.

There are $N$ complex numbers $z_1, \dots, z_N$. For $i=1,2, \dots, N$, $z_i$ can be expressed as $z_i = x_i + y_i \sqrt{-1}$ using integers $x_i, y_i$. Here, $z_i \neq 0$.

Let $S$ be $$S := \sum_{i=1}^{N-1} \sum_{j=i+1}^N \left|\dfrac{z_i}{z_j} - \dfrac{z_j}{z_i} \right|^2$$ Then it can be proved that $S$ is a rational number. Find $S \pmod{998244353}$.

Here, for a complex number $w$, $\left| w \right|$ denotes the absolute value of $w$ in the sense of complex numbers.

Solve $T$ test cases.

Notes

Under the constraints of this problem, for $S$ there exist integers $A,B$ satisfying the following.

  • $A$ is not a multiple of $998244353$.
  • $A \times S = B$.

For these $A,B$, there exists a unique integer $C$ with $0$ or greater and less than $998244353$ such that $A \times C \equiv B \pmod{998244353}$, and using this $C$, we define $S \pmod{998244353}:=C$.

Note that there are many possible choices of an integer $A$ that is not a multiple of $998244353$ and an integer $B$ such that $A \times S =B$, but $C$ does not depend on the choice of $A,B$ and is determined only by $S$.

Constraints

  • $1 \leq T \leq 10^5$.
  • Constraints for each test case
    • $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)$
  • Constraints for each test file
    • The sum of $N$ over the $T$ test cases is at most $3 \times 10^5$.
  • All input values are integers.

Input

$T$
$\textrm{Testcase}_1$
$\textrm{Testcase}_2$
$\vdots$
$\textrm{Testcase}_T$
Each test case is given in the following format.
$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

Output

The output consists of $T$ lines. On the $t~(1 \leq t \leq T)$-th line, print the answer to the $t$-th test case.

Do not forget the newline at the end.

Sample

Sample 1
Input
3
3
1 1
2 0
1 2
2
4 -6
4 -6
5
46 46
12345 6789
-14142 13562
-13579 2468
0 1
Output
149736660
0
106880605

  • [Test case $1$]

    We have $z_1 = 1 + \sqrt{-1}, z_2 = 2, z_3 = 1 + 2 \sqrt{-1}$. Then,

    $$\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}$$ so $S=\dfrac{5}{2}+\dfrac{13}{10}+\dfrac{13}{4}=\dfrac{141}{20}$.

    Also, since $20 \times S = 141$ and $20 \times 149736660 \equiv 141 \pmod{998244353}$, we have $S \pmod{998244353} = 149736660$.

  • [Test case $2$]

    Since $z_1=z_2=4 - 6 \sqrt{-1}$, we have $S=0$.

Sample 2
Input
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
Output
591212021

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。