मान लीजिए कि हमारे पास पहले 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 के साथ एक सरणी
- 2 से n+1 की श्रेणी में n के लिए, करें
- B :=A, A :=केवल एक तत्व 1 के साथ एक सरणी
- D:=C, C:=केवल एक तत्व 1 के साथ एक सरणी
- x के लिए श्रेणी 1 से न्यूनतम (k+1 और 1 से n तक की सभी संख्याओं का योग)
- सम्मिलित करें (ए का अंतिम तत्व + (बी [एक्स] जब एक्स <बी का आकार अन्यथा 0) - (बी [एक्स-एन] जब 0 <=एक्स-एन अन्यथा 0)) मॉड पी) ए के अंत में
- x श्रेणी 1 से n-2 के लिए, करें
- सी के अंत में ((D[x]+(n-1)*D[x-1]) mod p) डालें
- C के अंत में (n * D का अंतिम तत्व) mod p डालें
- ए [इंडेक्स के मॉड 2 से के] के सभी तत्वों का रिटर्न योग) मॉड पी और सी [न्यूनतम एन -1 और के]
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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