| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 16 | 8 | 8 | 66.667% |
You are given two arrays $b$ and $c$ of length $n,ドル consisting of non-negative integers. Construct $n \times n$ matrix $A$ as $A_{ij} = b_i \oplus c_j$. Find the determinant of $A$ modulo 998ドル,244円,353円$.
Each test contains multiple test cases. The first line contains an integer $t$ (1ドル \le t \le 1000$) --- the number of test cases. The descriptions of the $t$ test cases follow.
The first line of each test case contains one integer $n$ (1ドル \le n \le 5000$).
The second line contains the array $b_1, b_2, \ldots, b_n$ (0ドル \le b_i < 2^{60}$).
The third line contains the array $c_1, c_2, \ldots, c_n$ (0ドル \le c_i < 2^{60}$).
The sum of $n$ over all test cases does not exceed 10ドル,000円$.
For each test case, print the determinant of matrix $A$ modulo 998ドル,244円,353円$.
3 2 2 5 4 1 1 1000000000000000001 987467354324283836 4 1 2 3 4 1 2 3 4
21 214139910 998244129
First test case:
$ \begin{vmatrix} 6 & 3\\ 1 & 4 \end{vmatrix} = 6 \cdot 4 - 1 \cdot 3 = 21 $
Second test case:
$ \begin{vmatrix} 23,792円,195円,055円,071円,677円 \end{vmatrix} = 23,792円,195円,055円,071円,677円 $
23ドル,792円,195円,055円,071円,677円 \bmod 998,244円,353円 = 214,139円,910円$
Third test case:
$ \begin{vmatrix} 0 & 3 & 2 & 5 \\ 3 & 0 & 1 & 6 \\ 2 & 1 & 0 & 7 \\ 5 & 6 & 7 & 0 \end{vmatrix} = 3 \cdot 3 \cdot 7 \cdot 7 - 3 \cdot 1 \cdot 7 \cdot 5 - 3 \cdot 6 \cdot 2 \cdot 7 - 2 \cdot 3 \cdot 7 \cdot 6 + 2 \cdot 6 \cdot 2 \cdot 6 - 2 \cdot 6 \cdot 1 \cdot 5 - 5 \cdot 3 \cdot 1 \cdot 7 - 5 \cdot 1 \cdot 2 \cdot 6 + 5 \cdot 1 \cdot 1 \cdot 5 = $
$ = 441 -ひく 105 -ひく 252 -ひく 252 +たす 144 -ひく 60 -ひく 105 -ひく 60 +たす 25 =わ -ひく224 $
$(-224) \bmod 998,244円,353円 = 998,244円,129円$