मान लीजिए कि हमारे पास n गेंदें हैं जिन्हें एक सरणी संख्या द्वारा क्रमांकित किया गया है, जिसका आकार n है और अंक [i] गेंद की संख्या का प्रतिनिधित्व करता है। अब हमारे पास एक और मान k है। प्रत्येक मोड़ में हम n विभिन्न गेंदों से k गेंदें लेते हैं और k गेंदों के अधिकतम और न्यूनतम मानों का अंतर पाते हैं और अंतर को एक तालिका में संग्रहीत करते हैं। फिर इन k गेंदों को फिर से उस बर्तन में डालें और फिर से तब तक चुनें जब तक कि हम सभी संभावित चयनों का चयन न कर लें। अंत में तालिका से सभी अंतरों का योग ज्ञात कीजिए। अगर उत्तर बहुत बड़ा है, तो परिणाम मोड 10^9+7 लौटाएं।
इसलिए, यदि इनपुट n =4 k =3 अंक =[5, 7, 9, 11] जैसा है, तो आउटपुट 20 होगा क्योंकि संयोजन हैं -
- [5,7,9], अंतर 9-5 =4
- [5,7,11], अंतर 11-5 =6
- [5,9,11], अंतर 11-5 =6
- [7,9,11], अंतर 11-7 =4
तो 4+6+6+4 =20.
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- म :=10^9 + 7
- आमंत्रण:=तत्वों के साथ एक नई सूची [0, 1]
- 2 से n की श्रेणी में i के लिए, करें
- आमंत्रण के अंत में (m - तल (m / i) * inv[m mod i] mod m) डालें
- comb_count :=1
- res :=0
- के-1 से n-1 की श्रेणी में चयन करने के लिए
- res :=res +(nums[pick] - nums[n - 1 - pick]) * Comb_count mod m
- res :=res mod m
- comb_count :=Comb_count *(+1 चुनें) mod m * inv[pick + 2 - k] mod m
- रिटर्न रेस
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
def solve(n, k, nums): m = 10**9 + 7 inv = [0, 1] for i in range(2, n + 1): inv.append(m - m // i * inv[m % i] % m) comb_count = 1 res = 0 for pick in range(k - 1, n): res += (nums[pick] - nums[n - 1 - pick]) * comb_count % m res %= m comb_count = comb_count * (pick + 1) % m * inv[pick + 2 - k] % m return res n = 4 k = 3 nums = [5, 7, 9, 11] print(solve(n, k, nums))
इनपुट
4, 3, [5, 7, 9, 11]
आउटपुट
20