부분집합 친화도
플래티넘 I의견: 0
\(B\)개의 속성이 있다. \(N\)개의 객체가 주어지며 각 객체 \(i\)는 보유한 속성 집합을 \(B\)비트 정수 \(a_i\)로(켜진 비트 = 보유 속성) 나타내고, 가중치 \(w_i\)를 가진다.
객체 \(j\)의 속성 집합이 객체 \(i\)의 속성 집합의 부분집합일 때(즉 \(a_j \,\&\, a_i = a_j\)) \(j\)는 \(i\)에게 친화적이라고 한다. 각 객체 \(i\)에 대해, \(i\)에게 친화적인 모든 객체 \(j\)의 가중치 합 \(f_i\)를 구하여라(자기 자신도 자신의 부분집합이므로 포함된다).
출력으로는 모든 \(i\)에 대한 \(\big(i \cdot f_i\big)\)의 합을 \(2^{64}\)로 나눈 나머지를 출력한다 (객체는 \(1\)번부터 번호를 매긴다). 이렇게 하면 답을 한 줄로 요약할 수 있다.
각 쌍을 비교하는 \(O(N^2)\) 풀이나 마스크마다 모든 부분 마스크를 도는 \(O(3^B)\) 풀이는 통과할 수 없다.
\(1 \le B \le 20\)
\(1 \le N \le 200{,}000\)
\(0 \le a_i < 2^B\)
\(1 \le w_i \le 10^9\)
첫 줄에 속성 수 \(B\)와 객체 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각 객체의 속성 마스크 \(a_i\)와 가중치 \(w_i\)가 주어진다 (\(0 \le a_i < 2^B\)).
\(\sum_{i=1}^{N} i \cdot f_i\) 를 \(2^{64}\)로 나눈 나머지를 출력한다.
2 4
0 1
1 2
3 3
2 4
57객체 1=∅(w=1), 2={속성0}(w=2), 3={속성0,1}(w=3), 4={속성1}(w=4). \(f_1\)=1(자기). \(f_2\)=1+2=3(∅,자기). \(f_4\)=1+4=5. \(f_3\)=1+2+4+3=10(모든 부분집합). 합 \(1\cdot1+2\cdot3+3\cdot10+4\cdot5=57\).
1 2
0 5
1 7
29속성 1개. 객체1=∅(w=5), 객체2={속성0}(w=7). \(f_1\)=5, \(f_2\)=5+7=12. 합 \(1\cdot5+2\cdot12=29\).
riseoj 작성
출처 Original
평가 및 의견
부분집합 친화도
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
부분집합 친화도