10030. Real / Fake Thing

I'm a slow walker, but I never walk backwards.

題目描述

「偽物比真物更有價值」—貝木泥舟 「真物和偽物一樣有價值」—忍野咩咩 「偽娘比真娘更有價值」—精英島民

任兩個物品的相似度 $sim(A, B) = \frac{\vert A \cap B\vert }{\vert A \cup B\vert }$,換句話說把 $A$ 具有的特徵和 $B$ 具有的特徵類型取交集、聯集個數,相除就能得到其相似度。例如有 5 個特徵,若 A 表示成 11001、B 表示成 01100,$sim(A, B) = \frac{\vert {2}\vert }{\vert {1, 2, 3, 5}\vert } = 0.25$。

現在盤面上有 N 個物品、M 種特徵,請問相似度大於等於 0.8 的相似對數 $S$ 有多少種。為了讓這一題更有趣味,算法允許偽物,輸出 $\frac{S}{N(N-1)/2} \times 100 \text{%}$。

輸入格式

每組測資,第一行會有兩個整數 $N, M$,表示有 $N$ 個物品、$M$ 種特徵。

接下來會有 $N$ 行,每一行上會有 $M$ 個 01 字符,第 $i$ 行上的第 $j$ 個字元,表示第 $i$ 個物品,是否擁有特徵 $j$。

  • $1 \lt N \le 1024, 0 \lt M \le 512$

輸出格式

對於每一組輸出一行,輸出一個小數點兩位,相似度高於 0.8 的對數 / 總對數的百分比。

範例輸入

8 10
0111101101
0111101100
0111101100
0111101101
1100101010
0111101100
0111101100
0011101111
 
8 10
1111101100
1011101100
1010101100
1010111010
0100110100
1011101100
1110110000
1011111100

範例輸出

53.57
25.00

提示

bitset / bitmask

Discussion