Cho mảng A kích thước n, thực hiện p lần hoán vị ngẫu nhiên 2 phần tử và q lần đảo ngược ngẫu nhiên mảng con. Sau đó chọn ngẫu nhiên mảng con A[l..r] (l < r) và tính tổng S. Tìm kỳ vọng của S.
Ví dụ: A=[1,2,3], p=1, q=1 → kỳ vọng ≈ 4.667.
Phương pháp ma trận Markov
- Mô hình hóa phép hoán vị và đảo ngược bằng ma trận chuyển trạng thái xác suất.
- Nhân ma trận lặp
plần cho hoán vị,qlần cho đảo ngược. - Tính kỳ vọng tổng mảng con từ vector xác suất cuối cùng.
Ví dụ mã nguồn
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 = [swapvalm]*n
revrow = [2*(min(i, j, n-i-1, n-j-1) + 1)/(n*(n-1)) for j in range(n)]
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 = sum(dotv[i]*A[i] for i in range(n))
return tot
A = [1,2,3]
p = 1
q = 1
print(solve(A, p, q)) # 4.666...
Đầu vào / Đầu ra
Input: [1,2,3], 1, 1
Output: 4.666666666666667