Anzahl einzigartiger Arrays
Angenommen, es gibt
n Arrays, wobei jedes Array eine Länge von l (l ganze Zahlen) hat. Gesucht ist die Anzahl unterschiedlicher Arrays. Zwei Arrays gelten dann als unterschiedlich, wenn sie sich in mindestens einem Element unterscheiden.Beachte, dass ein paarweises Vergleichen aller Arrays sehr zeitaufwändig sein kann. Stattdessen kannst du jedes Array mithilfe einer selbst gewählten Hashfunktion in einen Hashwert umwandeln und diese Hashwerte miteinander vergleichen.
Anschließend kannst du ein großes Array der Größe
m anlegen und es zunächst mit Nullen füllen. Jedes Mal, wenn du einen Hashwert berechnest, markierst du die entsprechende Position im Array mit einer Eins. Am Ende ermittelst du, wie viele Einträge in diesem großen Array auf Eins gesetzt sind.Wichtig ist, dass du die Hashfunktion modulo
m anwendest. So sind die Indizes innerhalb des Bereichs [0; m).Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n (1 ≤ n ≤ 1000) und l (1 ≤ l ≤ 1000).Die nächsten
n Zeilen enthalten jeweils l durch Leerzeichen getrennte ganze Zahlen (0 ≤ ≤ ).Ausgabe
Das Programm soll die Anzahl der einzigartigen Arrays ausgeben.
Beispiele
Input | Output |
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 |
Hinweis
Wenn die Hashfunktion nicht gut genug ist und es immer noch zu Kollisionen kommt, versuche es mit zwei verschiedenen Hashfunktionen – so wird der Algorithmus doppelt so widerstandsfähig gegenüber Kollisionen.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB