Tóm tắt: Cho n nhóm với Ai phần tử (Các phần tử khác nhau phân biệt); 0 <= Ai <= 30; có q thao tác thuộc 2 loại:
+ CA
B
-> Số phần tử ở chỉ số A (vị trí A) giờ sẽ thành B phần tử
+ Qu
v
-> Gọi S là tổng số phần tử từ vị trí u -> v. Trả về số cách chia S phần tử vào (v-u+1) nhóm, sao cho số phần tử nhóm có nhiều phần tử nhất nhiều hơn số phần tử nhóm có ít phần tử nhất ít hơn 2
VD: 2 phần tử, 2 nhóm -> 2 cách chia
Dữ liệu: q<=100000; n<=100000
Input:
8
2 1 1 2 1 2 2 2
4
C 2 2
Q 5 7
Q 3 3
Q 4 4
Output:
90
1
1
Đầu tiên cần xử lý truy vấn C ta dùng cấu trúc dữ liệu cây IT với mỗi thao tác C ta mất O(log(n)), với mỗi thao tác Q ta lấy tổng phần tử nhóm u->v với O(log(n))
Với mỗi thao tác Q bạn có thể hỏi mấy bạn chuyên toán công thức tính số cách chia S phần tử khác nhau vào N nhóm hoặc đọc cách của mình (Mình gà giải thích nên khó hiểu chút):
- Gọi S số phần tử, N là số nhóm cần chia, K = S/N (số phần tử mỗi nhóm trừ đi S/N - S%N)
- Nhận định rằng sẽ có S%N nhóm có số phần tử lớn hơn N-S%N nhóm là 1 phần tử
-S(C)K
(Tổ hợp chập K của S)
- Với N-S%N nhóm có số phần tử bé nhất ta có:S(C)K . (S-k)(C)K . (S-2k)(C)K .... (S-(N-S%N-1).k)(C)K
- Gọi S-(N-S%N).k = P
- Với S%N nhóm còn lại ta có:(P)(C)(k+1) . (P-(k+1))(C)(k+1) . (P-2(k+1))(C)(k+1) .... (P-(S%N - 1).k)(C)(k+1)
- Số cách =S(C)K . (S-k)(C)K . (S-2k)(C)K .... (S-(N-S%N-1).k)(C)K
.(P)(C)(k+1) . (P-(k+1))(C)(k+1) . (P-2(k+1))(C)(k+1) .... (P-(S%N - 1).k)(C)(k+1)
- Sau đó bạn có thể tự đặt tay vào rút gọn đống trên về một công thức gọn là:n! / [(n - (k+1).(S%N) - k.(N-S%N))! pow((k+1)!, (S%N)) pow(k!, (N-S%N))]
Nếu bạn không hiểu hoặc quá lười bạn có thể nhờ một đứa học sinh cấp 2 rút gọn hộ
- Để tính pow nhanh ta có thể dùng thuật toán chia để trị
- Để tính được(1/X)%mod
ta dùng Fermat nhỏ
Như vậy là đã giải được bài trên với thuật O(n + q.log2(n))
Nguồn: Bài tập ôn thầy Lê Thanh Bình - Hải Dương - T11/2019