레이팅 미적용*참고: 이 문제의 메모리 제한은 기본의 두 배인 512MB이다.*
농부 존의 \(N\)(\(1\le N\le 5\cdot 10^5\))마리 소들은 각자 모두 0은 아닌 길이 \(K\)(\(1\le K\le 20\))의 비트 문자열을 하나씩 배정받았다. 서로 다른 소가 같은 비트 문자열을 배정받을 수도 있다.
두 비트 문자열의 자카드 유사도는 비트 단위 교집합의 켜진 비트 수를 비트 단위 합집합의 켜진 비트 수로 나눈 값으로 정의된다. 예를 들어, 비트 문자열 \(\texttt{11001}\)과 \(\texttt{11010}\)의 자카드 유사도는 \(2/4\)이다.
각 소에 대해, 그 소의 비트 문자열과 자기 자신을 포함한 \(N\)마리 소들의 비트 문자열 각각과의 자카드 유사도의 합을 \(10^9+7\)로 나눈 나머지로 출력한다. 구체적으로, 그 합이 서로소인 정수 \(a\)와 \(b\)에 대해 유리수 \(a/b\)와 같다면, \(bx-a\)가 \(10^9+7\)로 나누어떨어지는 \([0,10^9+7)\) 범위의 유일한 정수 \(x\)를 출력한다.
문제 제공: Benjamin Qi
배점
- 입력 2-15: \(K\in \{10,15,16,17,18,19,20\}\) 각각에 대해 테스트 케이스가 두 개씩 있다.
문제 제공: Benjamin Qi
첫째 줄에 \(N\)과 \(K\)가 주어진다.
다음 \(N\)개의 줄에 각각 정수 \(i\in (0,2^K)\)가 주어지며, 이는 \(i\)의 길이 \(K\) 이진 표현에 대응하는 소를 나타낸다.
4 2
1
1
2
3500000006
500000006
500000005
500000006The cows are associated with the following bitstrings:
\([\texttt{01}, \texttt{01}, \texttt{10}, \texttt{11}]\).
For the first cow, the sum is
\(\text{sim}(1,1)+\text{sim}(1,1)+\text{sim}(1,2)+\text{sim}(1,3)=1+1+0+1/2\equiv 500000006\pmod{10^9+7}\).
The second cow's bitstring is the same as the first cow's, so her sum is the
same as above.
For the third cow, the sum is
\(\text{sim}(2,1)+\text{sim}(2,1)+\text{sim}(2,2)+\text{sim}(2,3)=0+0+1+1/2\equiv 500000005\pmod{10^9+7}\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > December > Platinum