मान लीजिए हमारे पास पहले n प्राकृतिक संख्याओं वाली एक सरणी A है। हमें पता लगाना है कि A पर सटीक k आसन्न स्वैप के बाद हम कितने अनुक्रम (S1) प्राप्त कर सकते हैं? और A पर अधिकतम k स्वैप के बाद हम कितने अनुक्रम (S2) प्राप्त कर सकते हैं? यहां आसन्न स्वैप का अर्थ इंडेक्स i और i+1 पर तत्वों को स्वैप करना है।
तो, यदि इनपुट n = 3, k = 2 है, तो आउटपुट 3, 6 होगा क्योंकि:
मूल सरणी [1, 2, 3] थी
- 2 आसन्न स्वैप के बाद: हम [1, 2, 3], [2, 3, 1], [3, 1, 2] प्राप्त कर सकते हैं। तो S1 = 3
- अधिकतम 2 स्वैप के बाद:
- 0 स्वैप के बाद: [1, 2, 3]
- 1 स्वैप के बाद: [2, 1, 3], [3, 2, 1], [1, 3, 2]
- 2 स्वैप के बाद: [1, 2, 3], [2, 3, 1], [3, 1, 2]
तो S2 = 6
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- p = 10^9+7
- A := केवल एक तत्व 1 वाली सरणी
- C := केवल एक तत्व 1 वाली सरणी
- n को 2 से n+1 तक की रेंज में, करें
- B := A, A := केवल एक तत्व 1 वाली सरणी
- D := C, C := केवल एक तत्व 1 वाली सरणी
- x को 1 से न्यूनतम (k+1 और 1 से n तक सभी संख्याओं का योग) तक की रेंज में
- (A के अंतिम तत्व + (B[x] जब x, B के आकार से कम हो अन्यथा 0) - (B[x-n] जब 0 <= x-n अन्यथा 0)) mod p को A के अंत में डालें
- x को 1 से n-2 तक की रेंज में, करें
- ((D[x]+(n-1)*D[x-1]) mod p) को C के अंत में डालें
- (n * D के अंतिम तत्व) mod p को C के अंत में डालें
- A[इंडेक्स k mod 2 से k] के सभी तत्वों का योग mod p और C[n-1 और k का न्यूनतम] लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
p = 10**9+7 def solve(n, k): A = [1] C = [1] for n in range(2,n+1): B = A A = [1] D = C C = [1] for x in range(1,min(k+1,n*(n-1)//2+1)): A.append((A[-1] + (B[x] if x<len(B) else 0) - (B[x-n] if 0<=x-n else 0)) % p ) for x in range(1,n-1): C.append((D[x]+(n-1)*D[x-1]) % p) C.append(n*D[-1] % p) return sum(A[k%2:k+1:2]) % p,C[min(n-1,k)] n = 3 k = 2 print(solve(n, k))
इनपुट
3, 2
आउटपुट
3, 6
