Bài tập tin học
FMAGIC - Khu rừng ma thuật (3 sao)

Được viết bởi: Codeforces


Đề bài: Xem đề bài


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:
+ C A B -> Số phần tử ở chỉ số A (vị trí A) giờ sẽ thành B phần tử
+ Q u 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

Submit



Solution by SonDepZai


Đầ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))


Code:




Nguồn: Bài tập ôn thầy Lê Thanh Bình - Hải Dương - T11/2019

Posted on September 26, 2020 10:32:10 PM


2
Donate free




Đăng nhập để tham gia thảo luận! Hoặc bạn có thể bình luận bằng facebook ở dưới.