#PU1452. USACO 2024 December Contest, Platinum — Problem 1. All Pairs Similarity

    ID: 1338 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec24来源:usaco.orgscoring:equal_test_cases线段树

USACO 2024 December Contest, Platinum — Problem 1. All Pairs Similarity

USACO 2024 December Contest, Platinum — Problem 1. All Pairs Similarity

题目描述

Note: The memory limit for this problem is 512MB, twice the default. Farmer John's NN (1≤N≤5⋅1051\le N\le 5\cdot 10^5) cows are each assigned a bitstring of length KK that is not all zero (1≤K≤201\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 11001\texttt{11001} and 11010\texttt{11010} would be 2/42/4. For each cow, output the sum of her bitstring's Jaccard similarity with each of the NN cows' bitstrings including her own, modulo 109+710^9+7. Specifically, if the sum is equal to a rational number a/ba/b where aa and bb are integers sharing no common factors, output the unique integer xx in the range [0,109+7)[0,10^9+7) such that bx−abx-a is divisible by 109+710^9+7.

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

Inputs 2-15: There will be two test cases for each of K∈{10,15,16,17,18,19,20}K\in \{10,15,16,17,18,19,20\}. Problem credits: Benjamin Qi

样例

样例 1

4 2
1
1
2
3
500000006
500000006
500000005
500000006
The 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}$.