HILO

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie có một số bí mật $x + 0.5$ , trong đó $x$ là một số nguyên nằm trong khoảng từ $0$ đến $N$ ( $0 \leq x \leq N$ ). Elsie cố gắng đoán số này bằng cách hỏi "số $i$ cao hay thấp?" cho các số nguyên từ $1$ đến $N$ .

Nếu $i > x + 0.5$ : Bessie trả lời "HI".
Nếu $i < x + 0.5$ : Bessie trả lời "LO".

Elsie sử dụng chiến lược sau: cô tạo một hoán vị $p_{1}, p_{2}, \dots, p_{N}$ của các số từ $1$ đến $N$ , rồi đoán lần lượt $p_{1}, p_{2}, \dots$ Tuy nhiên, cô bỏ qua lần đoán $p_{i}$ nếu kết quả đã rõ ràng, cụ thể:

Bỏ qua $p_{i}$ nếu đã từng đoán $p_{j} < p_{i}$ và nhận "HI" (tức $p_{j}$ đã lớn hơn $x + 0.5$ , nên $p_{i}$ cũng vậy).
Bỏ qua $p_{i}$ nếu đã từng đoán $p_{j} > p_{i}$ và nhận "LO" (tức $p_{j}$ đã nhỏ hơn $x + 0.5$ , nên $p_{i}$ cũng vậy).

Nối tất cả các phản hồi lại thành một xâu ký tự (ví dụ "HILOHILO"). Đếm số lần xâu con "HILO" xuất hiện trong xâu phản hồi.

Cho $N$ và $x$ , tính tổng số lần "HILO" xuất hiện trên tất cả $N!$ hoán vị mà Elsie có thể chọn, modulo $10^{9} + 7$ .

Dữ liệu vào

Một dòng chứa hai số nguyên $N$ và $x$ .

Dữ liệu ra

In ra một số nguyên duy nhất: tổng số lần "HILO" xuất hiện trên tất cả các hoán vị, modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq N \leq 5000$
$0 \leq x \leq N$

Ví dụ

Input	Output	Giải thích
4 2	17	Số bí mật là $2.5$ . Ví dụ với hoán vị $(4, 1, 3, 2)$ : đoán $4$ ("HI"), đoán $1$ ("LO"), đoán $3$ (bỏ qua vì $1$ đã "LO" và $1 < 3$ ... nhưng $4$ đã "HI" và $4 > 3$ ? Không, $3 < 4$ nên "HI" từ $4$ không cho biết kết quả $3$ . Thực tế $3 > 2.5$ nên đoán $3$ cho "HI", đoán $2$ bỏ qua vì $1$ đã "LO". Xâu: "HILOHI", có $1$ lần "HILO". Tổng trên tất cả $24$ hoán vị là $17$ .
60 10	508859913	$N = 60$ , $x = 10$ . Kết quả modulo $10^{9} + 7$ .

Ghi chú

Lưu ý rằng Elsie bỏ qua lần đoán $p_{i}$ chỉ khi có thể suy ra kết quả từ các lần đoán trước. Cụ thể, nếu đã biết HI cho một giá trị nhỏ hơn $p_{i}$ , hoặc LO cho một giá trị lớn hơn $p_{i}$ , thì kết quả đoán $p_{i}$ đã hiển nhiên.

Bình luận

Không có bình luận tại thời điểm này.