สมมติว่าเรามีอาร์เรย์ A ที่มีจำนวนธรรมชาติ n ตัวแรก เราต้องหาจำนวนลำดับ (S1) ที่เราจะได้รับหลังจากสลับ k ตัวติดกันบน A หรือไม่? และเราสามารถหาลำดับ (S2) ได้มากที่สุดกี่ครั้งใน k swap บน A? ที่นี่การแลกเปลี่ยนที่อยู่ติดกันหมายถึงการสลับองค์ประกอบที่ดัชนี 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
