시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 4 | 2 | 2 | 66.667% |
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$.