Đếm Kiện Cỏ Khô

Đ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

Cho $N$ cọc có chiều cao $h_{1}, h_{2}, \dots, h_{N}$ . Bạn có thể thực hiện một loại thao tác: nếu hai cọc liền kề có chiều cao chênh nhau đúng $1$ , hãy chuyển một đơn vị từ cọc cao hơn sang cọc thấp hơn (tức là giảm chiều cao cọc cao đi $1$ và tăng chiều cao cọc thấp lên $1$ ).

Hãy đếm số cấu hình $(h_{1}^{'}, h_{2}^{'}, \dots, h_{N}^{'})$ phân biệt có thể đạt được sau khi thực hiện các thao tác trên một số lần tùy ý (có thể không thực hiện), kể cả cấu hình ban đầu. Kết quả lấy modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $T$ — số lượng test case.

Mỗi test case gồm hai dòng:

Dòng đầu: số nguyên $N$ .
Dòng thứ hai: $N$ số nguyên $h_{1}, h_{2}, \dots, h_{N}$ .

Dữ liệu ra

In ra $T$ dòng, mỗi dòng chứa số cấu hình có thể đạt được của test case tương ứng, modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq T \leq 10$
$1 \leq N \leq 5000$
$1 \leq h_{i} \leq 10^{9}$
Tổng $N$ qua tất cả các test case không vượt quá $5000$

Ví dụ

Input	Output	Giải thích
7 4 2 2 2 3 4 3 3 1 2 4 5 3 4 2 6 3 3 1 1 2 2 6 1 3 3 4 1 2 6 4 1 2 3 5 4 10 1 5 6 6 6 4 2 3 2 5	4 4 5 15 9 8 19	Với dãy $(2, 2, 2, 3)$ : bốn cấu hình đạt được là $(2, 2, 2, 3)$ , $(2, 2, 3, 2)$ , $(2, 3, 2, 2)$ , $(3, 2, 2, 2)$ .
10 10 447773962 773442532 122816 137572579 324627123 157577940 253498609 99147813 425825313 199995380 10 416515986 416515986 416515987 416515987 416515988 416515988 416515989 416515989 416515988 416515989 10 563229302 563229301 563229301 563229302 563229301 563229300 563229300 563229301 563229302 563229302 10 490919926 490919926 490919926 490919925 490919926 490919925 490919926 490919927 490919928 490919929 10 861954306 861954305 861954304 861954305 861954305 861954306 861954307 861954308 861954309 861954308 10 890779831 890779830 890779829 890779828 890779827 890779828 890779829 890779828 890779828 890779828 10 721183090 721183091 721183091 721183091 721183090 721183091 721183090 721183089 721183088 721183089 10 841077511 841077512 841077512 841077511 841077510 841077511 841077511 841077512 841077512 841077513 10 320506887 320506886 320506886 320506887 320506886 320506885 320506884 320506884 320506884 320506885 10 103264177 103264176 103264177 103264176 103264175 103264174 103264174 103264173 103264172 103264173	1 186 210 133 150 133 175 231 155 154	Với dãy gồm $10$ phần tử chỉ gồm các giá trị liên tiếp nhau (chênh nhau $\leq 1$ ), số hoán vị hợp lệ được tính qua bài toán đếm thứ tự topo.

Ghi chú

Thao tác cho phép tương đương với hoán đổi hai phần tử liền kề có giá trị chênh nhau đúng $1$ . Từ đó, bài toán quy về đếm số thứ tự topo của một đồ thị có hướng: tồn tại cạnh $i \to j$ (với $i < j$ ) khi $| h_{i} - h_{j} | \neq 1$ (tức là không thể hoán đổi).

Bình luận

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