สมมติว่าเรามีอาเรย์ A ขนาด n และค่า p, q สามารถดำเนินการ 2 แบบ:
- สุ่มเลือก (l, r) ที่ l < r แล้วสลับ A[l] กับ A[r]
- สุ่มเลือก (l, r) ที่ l < r แล้วกลับลำดับ subarray A[l..r]
หลังทำ operation แบบแรก p ครั้ง และแบบที่สอง q ครั้ง สุ่มเลือก l < r คำนวณ S = ผลรวม subarray A[l..r] หาค่าคาดหวังของ S
ตัวอย่าง A = [1,2,3] p = 1 q = 1 ผลลัพธ์ประมาณ 4.667
ขั้นตอนการแก้ปัญหา
- ใช้ Matrix Multiplication จำลองการกระจายความน่าจะเป็นของตำแหน่งแต่ละ index
- สร้าง transition matrix สำหรับ swap และ reverse
- ยกกำลัง matrix ตาม p และ q
- คำนวณ expected value จาก dot product กับ vector น้ำหนึก
ตัวอย่างโค้ด
def matmul(a, v, n):
toret = [0]*n
for i in range(n):
for j in range(n):
toret[i] += a[i][j]*v[j]
return toret
def solve(A, p, q):
n = len(A)
temp = []
swp = (n - 3)/(n - 1)
swapvalp = (pow(swp, p)*(n - 1) + 1)/n
swapvalm = (1 - pow(swp, p))/n
rev = []
dotv = []
for i in range(n):
swaprow = []
revrow = []
for j in range(n):
swaprow.append(swapvalm)
revrow.append(2*(min(i, j, n - i - 1, n - j - 1) + 1)/(n*(n - 1)))
swaprow[i] = swapvalp
revrow[i] = 1.0 - 2*((i + 1)*(n - i) - min(i + 1, n - i))/(n*(n - 1))
temp.append(swaprow)
rev.append(revrow)
dotv.append(2*((i + 1)*(n - i) - 1)/(n*(n - 1)))
A = matmul(temp, A, n)
for _ in range(q):
A = matmul(rev, A, n)
tot = 0.0
for i in range(n):
tot += dotv[i]*A[i]
return tot
A = [1,2,3]
p = 1
q = 1
print(solve(A, p, q))
อินพุต
[1,2,3], 1, 1
เอาต์พุต
4.666666666666667
