| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 502 | 201 | 127 | 34.605% |
$N$개의 집합 $S_1, S_2, \cdots, S_N$이 주어집니다.
$S_1, S_2, \cdots, S_N$ 중 $k$개를 고른 이후, 고른 집합들의 교집합의 크기를 생각합시다. $a_k$는 집합을 고르는 가능한 모든 ${N \choose k}$가지의 선택 방법 모두에 대해 교집합의 크기를 더한 값입니다. 수식으로는 다음과 같이 표현할 수 있습니다:
$$a_{k} := \sum_{\substack{\tau \subseteq \{1, 2, \cdots, N\} \\|\tau|=k}} \left|\bigcap_{i \in \tau} S_{i}\right|.$$
모든 $k=1, 2, \cdots, N$에 대해, $a_{k}$를 998ドル,244円,353円$ $(=119 \times 2^{23}+1)$으로 나눈 나머지를 구하세요. 998ドル,244円,353円$은 소수입니다.
첫 줄에 정수 $N$이 주어집니다. (1ドル\leq N\leq 1,円 000,円 000$)
다음 $N$개의 줄의 $i$번째 줄은 다음과 같이 주어지는 공백으로 구분된 정수입니다.
주어지는 집합의 크기의 합은 1ドル,円 000,円 000$을 넘지 않습니다. 즉, $\sum_{1\leq i\leq N}|S_{i}|\leq 1,円 000,円 000$입니다.
$N$개의 줄을 출력합니다. 모든 1ドル \leq k \leq N$에 대해, $k$번째 줄에 $a_{k}$를 998ドル,244円,353円$으로 나눈 나머지를 출력합니다.
3 2 1 2 2 2 3 3 1 2 3
7 5 1
$a_{1}$은 각각의 집합의 크기를 구해 모두 더하면 되므로 2ドル + 2 + 3 = 7$입니다.
$a_{2}$는 각 집합을 두 개씩 교집합한 뒤 크기를 더합니다. $S_{1} \cap S_{2} = \{2\},ドル $S_{1} \cap S_{3} = \{1, 2\},ドル $S_{2} \cap S_{3} = \{2, 3\}$이므로, 답은 1ドル + 2 + 2 = 5$입니다.
$a_{3}$는 모든 집합을 교집합한 뒤 크기를 구합니다. $S_{1} \cap S_{2} \cap S_{3} = \{2\}$이므로, 답은 1ドル$입니다.
Contest > solved.ac > solved.ac Grand Arena #3 > Division 2 E번