Tìm kiếm nhị phân?

Xem PDF




Tác giả:
Dạng bài
Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho hai số nguyên \(n\)\(x\). Hãy đếm số lượng dãy \(a\) độ dài \(n\), mỗi phần tử có giá trị trong khoảng \([1, n]\) và hàm sau có giá trị đúng:

binary_search(a, n, x)
    left = 1
    right = n
    while left <= right
        middle = (left + right) / 2
        if a[middle] == x then
            return true

        if a[middle] < x then
            left = middle + 1
        else
            right = middle - 1

    return false

Lưu ý rằng các phần tử của dãy được đánh chỉ số từ \(1\) và phép chia được thực hiện ở phần nguyên (làm tròn xuống).

Input

  • Một dòng duy nhất chứa hai số nguyên \(n\)\(x\) (\(1 \leq x \leq n \leq 10 ^ {12}\)).

Output

  • Một dòng duy nhất chứa một số nguyên là số lượng dãy \(a\) thỏa mãn sau khi chia lấy dư cho \(10 ^ 9 + 7\).

Scoring

  • Subtask 1 (20% số điểm): \(n \leq 7\).
  • Subtask 2 (20% số điểm): \(n \leq 10 ^ 3\).
  • Subtask 3 (30% số điểm): \(n \leq 10 ^ 6\).
  • Subtask 4 (30% số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input
3 2
Output
15
Note

Các dãy thỏa mãn là: \([1, 1, 2]\), \([1, 2, 1]\), \([1, 2, 2]\), \([1, 2, 3]\), \([2, 1, 2]\), \([2, 2, 1]\), \([2, 2, 2]\), \([2, 2, 3]\), \([2, 3, 1]\), \([2, 3, 2]\), \([2, 3, 3]\), \([3, 1, 2]\), \([3, 2, 1]\), \([3, 2, 2]\)\([3, 2, 3]\).


Bình luận

Không có bình luận nào.