अद्वितीय सरणियों (Arrays) की संख्या
आपको
n सरणियों का एक समूह दिया गया है, जिनमें प्रत्येक सरणी की लंबाई l है (l पूर्णांक). आपका कार्य यह निर्धारित करना है कि कुल कितनी अद्वितीय (unique) सरणियाँ हैं। दो सरणियाँ तब अलग मानी जाती हैं, जब उनमें कम-से-कम एक तत्त्व भिन्न हो।ध्यान दें कि सरणियों को एक-एक करके तुलना करना बहुत समय ले सकता है। आप अपनी पसंद के किसी भी हैश फ़ंक्शन (hash function) का उपयोग करके प्रत्येक सरणी का हैश निकाल सकते हैं और फिर हैश मानों की तुलना करने की कोशिश कर सकते हैं।
इसके बाद, आप
m आकार की एक बड़ी सरणी बना सकते हैं और उसे शून्य (0) से भर दें। हर बार जब आपको कोई हैश मान मिलता है, तो आप सरणी के उस इंडेक्स को 1 करके चिह्नित कर सकते हैं। अंत में, आप सरणी में मौजूद 1 के कुल स्थानों की गणना कर सकते हैं।ध्यान रखें कि हैश फ़ंक्शन के आउटपुट को
m से मॉड (modulo) किया जाना चाहिए, ताकि इंडेक्स [0; m) की सीमा में रहे।इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
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 |
Hint
यदि हैश फ़ंक्शन उतना मजबूत नहीं है और अभी भी टकराव (collisions) हो रहे हैं, तो दो अलग-अलग हैश फ़ंक्शनों से तुलना करने का प्रयास करें। इससे एल्गोरिथ्म टकराव के मुकाबले दोगुना मज़बूत हो जाता है।
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB