[POI] Hoán vị
ll931110
Link trên POI (tiếng Ba Lan): http://main.edu.pl/user.phtml?op=showtask&task=per&con=OI15
Lời giải:
Gọi tập hợp ban đầu là A = { a[1],a[2],...,a[n] }
Xét 1 tập hợp gồm a1 số 1, a2 số 2,..., ak số k. Số hoán vị thu được
sẽ là:
S = (a1 + a2 + ... + ak)! / [ (a1)! * (a2)! * ... * (ak)! ]
1/ Với công thức này, ta có lời giải O(n^3):
Duyệt từ 1 đến n, với mỗi i đếm số hoán vị P thỏa mãn: p[j] = a[j] với
1 <= j < i và p[i] < a[i] theo công thức trực tiếp như trên
2/ Ta cải tiến công thức này xuống O(n^2) bằng nhận xét sau:
Giả sử tập hợp đã cho có a1 số 1, a2 số 2,..., ak số k
Đặt a[1] = x. Số hoán vị P mà p[1] < x sẽ là
P = (a1 + a2 + ... + ak - 1)! * (1/[ (a1 - 1)! * (a2)! * ... * (ak)! ]
+ 1/[ (a1)! * (a2 - 1)! * ... * (ak)! ]+ ... + 1/[ (a1)! * (a2)! * ...
* ( a(x - 1) - 1)! * ... * (ak)!] )
= (a1 + a2 + ... + ak - 1)! * (a1 + a2 + ... + a(x - 1)) / ( (a1)! *
(a2)! * ... * (ak)! ) (**)
Chú ý rằng, a1 + a2 + ... + a(x - 1) chính bằng số lượng số nhỏ hơn x.
Nên từ công thức này, ta có thuật toán O(n^2):
Duyệt từ 1 đến n, với mỗi lần tính số hoán vị P thỏa mãn p[j] = a[j]
với 1 <= j < i và p[i] < a[i] bằng công thức (**)
3/ Cải tiến lần cuối cùng xuống O(n log n)
- Để tìm số lượng số nhỏ hơn x, có thể sử dụng 1 CTDL như Interval
Tree hoặc BIT
- Phần còn lại là làm sao có thể tính được (**) trong O( log n). Ta sẽ
làm điều đó bằng cách dựng 1 Interval tree để biểu diễn phân tích
thành thừa số nguyên tố của P. Cụ thể là:
Nếu P = p1^e1 * p2^e2 * ... * pk^ek thì:
- Đoạn [px,px] có giá trị là px^ex (nút lá bằng lũy thừa của px)
- Đoạn [px,py] có giá trị là [px,pt] * [p(t + 1),py] với t = (x + y)/
2; (nút cha bằng tích của 2 nút con, lấy modulo m)
Giả sử ta đã đếm số hoán vị đến i, và số hoán vị đếm được trong lần
thứ i là Sum[i]. Khi đó, có thể thấy ngay: Sum[i + 1] = Sum[i] / (n +
1 - i) * num[i] (num[i] là số lượng số còn lại bằng a[i] trong tập
hợp)
Để cập nhật 1 tích (hoặc 1 thương) vào interval tree, ta phân tích nó
ra thừa số nguyên tố, và với mỗi thừa số ấy, ta cộng (hoặc trừ) nó
tương ứng trong interval tree. Do các số cần cập nhật vào luôn <=
300000, nên chúng chỉ có tối đa 6 ước nguyên tố phân biệt, tức với mỗi
tích (hoặc thương), ta chỉ mất tối đa 6 lần cập nhật vào interval
tree.
Mà để tính P[i + 1] theo P[i], ta chỉ cần mất 1 lần nhân và 1 lần
chia, nên độ phức tạp để tính P[i + 1] theo P[i] sẽ là O(log n).
Vậy độ phức tạp của cả bài toán là O(n log n)./.