All Pairs Similarity
다이아몬드 III의견: 0
*Note: The memory limit for this problem is 512MB, twice the default.*
Farmer John's \(N\) (\(1\le N\le 5\cdot 10^5\)) cows are each assigned a bitstring
of length \(K\) that is not all zero (\(1\le K\le 20\)). Different cows may be
assigned the same bitstring.
The Jaccard similarity of two bitstrings is defined as the number of set bits in
their bitwise intersection divided by the number of set bits in their bitwise union.
For example, the Jaccard similarity of the bitstrings \(\texttt{11001}\) and
\(\texttt{11010}\) would be \(2/4\).
For each cow, output the sum of her bitstring's Jaccard similarity with each of
the \(N\) cows' bitstrings including her own, modulo \(10^9+7\). Specifically, if
the sum is equal to a rational number \(a/b\) where \(a\) and \(b\) are integers
sharing no common factors, output the unique integer \(x\) in the range
\([0,10^9+7)\) such that \(bx-a\) is divisible by \(10^9+7\).
Problem credits: Benjamin Qi
SCORING
- Inputs 2-15: There will be two test cases for each of \(K\in \{10,15,16,17,18,19,20\}\).
Problem credits: Benjamin Qi
The first line contains \(N\) and \(K\).
The next \(N\) lines each contain an integer \(i\in (0,2^K)\), representing a cow
associated with the length-\(K\) binary representation of \(i\).
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
평가 및 의견
All Pairs Similarity
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
All Pairs Similarity