Gọi \(f(l, r)\) là số lượng dãy \(a\) độ dài \(n\) sao cho vị trí tìm thấy \(x\) nằm trong đoạn \([l, r]\). Đặt \(m = \frac{l \, + \, r}{2}\). Dựa vào hàm được cho, ta có ba trường hợp:

• Vị trí tìm thấy \(x\) nằm trong đoạn \([l, m - 1]\):
  • Khi này, tại vị trí \(m\), ta phải đặt một số lớn hơn \(x\).
  • Còn trong đoạn \([m + 1, r]\), ta có thể đặt bất kì số nào.
  • Vậy số lượng dãy thỏa mãn là \(f(l, m - 1) \cdot (n - x) \cdot n ^ {r - m}\).
• Vị trí tìm thấy \(x\) là \(m\):
  • Khi này, tại vị trí \(m\), ta phải đặt \(x\).
  • trong đoạn \([l, m - 1]\) và \([m + 1, r]\), ta có thể đặt bất kì số nào.
  • Vậy số lượng dãy thỏa mãn là \(n ^ {r - l}\).
• Vị trí tìm thấy \(x\) nằm trong đoạn \([m + 1, r]\):
  • Khi này, tại vị trí \(m\), ta phải đặt một số nhỏ hơn \(x\).
  • Còn trong đoạn \([l, m - 1]\), ta có thể đặt bất kì số nào.
  • Vậy số lượng dãy thỏa mãn là \(f(m + 1, r) \cdot (x - 1) \cdot n ^ {m - l}\).

Vậy \(f(l, r) =\) \(f(l, m - 1) \cdot (n - x) \cdot n ^ {r - m}\) \(+\) \(n ^ {r - l}\) \(+\) \(f(m + 1, r) \cdot (x - 1) \cdot n ^ {m - l}\).

Nhận xét: Tất cả \(f(l, r)\) đều bằng nhau nếu có cùng giá trị \(r - l\).

Vậy ta có thể dùng std::map để lưu lại đáp án, khi gặp lại, ta chỉ cần trả về đáp án đã lưu.

Độ phức tạp: \(O(\log^2 n)\) do chỉ có tối đa \(O(\log n)\) giá trị \(r - l\) phân biệt.

Lưu ý: Vì \(n\) khá lớn nên rất dễ bị tràn số, cần cài đặt cẩn thận.