No.2651 [Cherry 6th Tune B] $\mathbb{C}$omplex комбинат
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun