Tutorial — Dãy đơn đỉnh

Hãy đếm số lượng giá trị phân biệt trong một dãy độ dài $n$ thỏa mãn điều kiện chứa đúng một cặp phần tử bằng nhau. Giá trị lớn nhất trong dãy có thể bị lặp lại hay không khi xét tính chất tăng ngặt và giảm ngặt quanh đỉnh?

Vì đỉnh lớn nhất chỉ xuất hiện một lần duy nhất, hai phần tử mang giá trị trùng nhau bắt buộc phải phân tách về hai phía đối diện của đỉnh. Hãy xét xem với mỗi giá trị còn lại trong tập $n - 1$ số đã chọn, có bao nhiêu vị trí khả dĩ giữa sườn tăng và sườn giảm.

Tổng số cách cấu thành dãy số bằng tích $\binom{m}{n - 1} \cdot (n - 2) \cdot 2^{n - 3}$ với $n \ge 3$, và bằng $0$ khi $n = 2$. Hãy sử dụng định lý Fermat nhỏ để tiền xử lý nghịch đảo modulo cho giai thừa và tính $2^{n - 3}$ bằng thuật toán lũy thừa nhanh trong thời gian $O(m + \log n)$.