페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8188
다국어

자카드 유사도 1초 1024MB

문제

존 농부의 소 N마리는 각각 길이가 K인 비트 문자열을 할당받았다. 이 비트 문자열은 모두 0이 아니며, 서로 다른 소들이 동일한 비트 문자열을 할당받을 수 있다.

자카드 유사도 공식 = \frac{|A \cap B|}{|A \cup B|}

두 비트 문자열의 자카드 유사도(Jaccard similarity)는 비트 단위로 교집합에서 1로 설정된 비트의 수를 그들의 비트 단위 합집합에서 1로 설정된 비트의 수로 나눈 값으로 정의된다. 예를 들어, 비트 문자열 11001과 11010의 자카드 유사도는 \frac{2}{4}​다.

각 소에 대해, 자신의 비트 문자열과 N마리 소의 비트 문자열 간의 자카드 유사도의 합을 출력하시오.

  • 단, 결과를 10^9+7로 나눈 나머지를 출력한다.

  • 구체적으로, 합이 \frac{a}{b}​라는 유리수로 표현된다면(단, a와 b는 서로소), [0,10^9+7) 범위에서 bx-a가 10^9+7로 나누어떨어지는 고유한 정수 x를 출력하시오.


입력

첫 줄에 두 정수 N과 K가 주어진다. (1≤N≤5⋅10^5; 1≤K≤20)

다음 N개의 줄에는 각각 i번째 소가 할당 받은 비트 문자열에 해당하는 정수 x_i가 주어지며, x_i는 (0, 2^K) 범위 내의 값으로 주어진다.


출력

각 소에 대하여 합을 10^9+7로 나눈 나머지를 출력한다.


예제1

입력
42
1
1
2
3
출력
500000006
500000006
500000005
500000006

소들은 각각 다음과 같은 비트 문자열들을 할당받았다: [01,01,10,11].

첫 번째 소의 자카드 유사도의 합 = sim(1,1)+sim(1,1)+sim(1,2)+sim(1,3)=1+1+0+1/2≡500000006(mod\ 10^9+7)

두 번째 소의 비트 문자열은 첫 번째 소와 같기에 그 자카드 유사도의 합은 동일하다.

세 번째 소의 자카드 유사도의 합 = sim(2,1)+sim(2,1)+sim(2,2)+sim(2,3)=0+0+1+1/2≡500000005(mod\ 10^9+7)


출처

USACO 2024 December Platinum

역링크