| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 19 | 4 | 4 | 28.571% |
You have an array of $n$ $k$-bit numbers $a_1, a_2, \ldots, a_n$.
You need to calculate $\sum_{i=1}^{n} \sum_{j=i+1}^{n} (a_i \oplus a_j)^x$.
Operation $a \oplus b$ is bitwise exclusive OR of two numbers $a$ and $b$.
Since the answer can be very large, output it modulo 998ドル,244円,353円$.
The first line of the input contains three integers $n, k, x$ (1ドル \leq n, k, n \cdot k \leq 300,000円,ドル 1ドル \leq x \leq 3$) --- length of an array, number of bits in each number and the power of exclusive OR operations results in the sum.
Next $n$ lines contain array elements.
The $i$-th of them contains string $s_0, s_1, \ldots, s_{k-1},ドル consisting of '0' and '1'.
Then $a_i = $ $\sum_{i=0}^{k-1} s_i \cdot 2^i$.
Print one number --- the remainder of division of the sum of $x$-th powers of exclusive OR results of all pairs of numbers in the array by 998ドル,244円,353円$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $n \leq 5000, k \leq 30$ |
| 2 | 5 | $n \cdot k \leq 5000$ |
| 3 | 5 | $k \leq 30,ドル $a_i = 2^{b_i}$ for some $b_i$ |
| 4 | 10 | $k \leq 20$ |
| 5 | 10 | $x = 1, n \cdot k \leq 300,000円$ |
| 6 | 15 | $x \leq 2, n \cdot k \leq 100,000円$ |
| 7 | 10 | $x \leq 2, n \cdot k \leq 300,000円$ |
| 8 | 15 | $n \cdot k \leq 100,000円$ |
| 9 | 10 | $n \cdot k \leq 200,000円$ |
| 10 | 15 | $n \cdot k \leq 300,000円$ |
3 3 1 101 001 001
2
2 6 3 101111 011001
19683
In the first sample array contains integers $[5, 4, 4],ドル and the answer is $(5 \oplus 4) + (5 \oplus 4) + (4 \oplus 4) = 1 + 1 + 0 = 2$.
In the second sample array contains integers $[61, 38],ドル and the answer is $(61 \oplus 38)^3 = 27^3 = 19683$.