ユニークな配列の数
与えられた n
個の配列があり、それぞれに l
個の整数が含まれているとします。このとき、ユニークな配列の数を求めてください。ここで「ユニーク」というのは、少なくとも1つの要素が異なる場合に別の配列として扱うということです。
すべての配列を1つひとつ直接比較すると時間がかかりすぎる可能性があります。そのため、配列をハッシュ関数などを用いてハッシュ化し、ハッシュ値を比較してみるという手があります。
次に、サイズ m
の大きな配列を用意して、すべての要素を0で初期化します。ハッシュ値が得られたら、そのハッシュ値を m
で割った余りをインデックスとして、その箇所を1に変更します。最後に、この配列の中にある1の数を数えることで、ユニークな配列の数を推定することができます。
ただし、ハッシュ関数はインデックス範囲を [0; m) に収めるために、必ず m
で剰余を取るようにしてください。
入力
最初の行には、2つの整数 n
(1 ≤ n ≤ 1000) と l
(1 ≤ l ≤ 1000) が与えられます。
続く n
行のそれぞれには、l
個の整数がスペース区切りで与えられます (0 ≤ ≤ )。
出力
ユニークな配列の数を出力してください。
例
入力 | 出力 |
---|---|
4 3 | 3 |
2 3 | 1 |
ヒント
もしハッシュ関数があまり良くなく、衝突(コリジョン)が多い場合は、2種類のハッシュ関数を使って比較してみると、衝突への耐性がさらに高まるでしょう。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB