มีอาร์เรย์ A = [1..n] หาจำนวนลำดับที่ได้หลังจากการสลับติดกัน (adjacent swaps) ทุก k ครั้ง (S1) และสูงสุด k ครั้ง (S2)
ตัวอย่าง: n=3, k=2 → S1=3, S2=6
ขั้นตอนการแก้ปัญหา
ใช้ DP นับจำนวน permutation ตามจำนวน inversion (สำหรับ adjacent swaps):
A[x]= จำนวน permutation ที่มี inversion = x หลังจากสลับติดกัน k ครั้งC[x]= จำนวน permutation ที่มี inversion ≤ x (สำหรับ at most k swaps)- อัปเดต DP โดยใช้ prefix sums และความสัมพันธ์เวียนเกิด
ตัวอย่างโค้ด Python
MOD = 10**9 + 7
def solve(n, k):
A = [1]
C = [1]
for n_val in range(2, n + 1):
B = A
A = [1]
D = C
C = [1]
for x in range(1, min(k + 1, n_val * (n_val - 1) // 2 + 1)):
val = (A[-1] + (B[x] if x < len(B) else 0) - (B[x - n_val] if 0 <= x - n_val else 0)) % MOD
A.append(val)
for x in range(1, n_val - 1):
C.append((D[x] + (n_val - 1) * D[x - 1]) % MOD)
C.append(n_val * D[-1] % MOD)
s1 = sum(A[k % 2 : k + 1 : 2]) % MOD
s2 = C[min(n - 1, k)]
return s1, s2
# ทดสอบ
n = 3
k = 2
print(solve(n, k)) # ผลลัพธ์: (3, 6)
อินพุตตัวอย่าง
3, 2
เอาต์พุตตัวอย่าง
3, 6
