ধরুন আমাদের প্রথম n প্রাকৃতিক সংখ্যা সহ একটি অ্যারে রয়েছে। আমাদের খুঁজে বের করতে হবে 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 সহ একটি অ্যারে
- এক্সের জন্য 1 থেকে সর্বনিম্ন পরিসরে (k+1 এবং 1 থেকে n পর্যন্ত সমস্ত সংখ্যার যোগফল)
- ঢোকান (A + এর শেষ উপাদান (B[x] যখন x <সাইজ B অন্যথায় 0) - (B[x-n] যখন 0 <=x-n অন্যথায় 0)) মোড p) A এর শেষে
1 থেকে n-2 রেঞ্জের x এর জন্য - করুন
- C এর শেষে ((D[x]+(n-1)*D[x-1]) mod p) ঢোকান
- ঢোকান (n * D এর শেষ উপাদান) C-এর শেষে mod p
এ
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
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
