ユニークな配列の数
与えられた
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
1 2 3
3 2 1
2 5 3
3 2 1 | 3 |
2 3
1 2 3 4
1 2 3 4 | 1 |
ヒント
もしハッシュ関数があまり良くなく、衝突（コリジョン）が多い場合は、2種類のハッシュ関数を使って比較してみると、衝突への耐性がさらに高まるでしょう。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB