TLEoj Contest #06 - Đếm hoán vị
Xem PDFTrong tiết toán thầy giáo cho lớp của bài toán sau:
Ta gọi 1 hoán vị độ dài n là 1 dãy số bao gồm n phần thử chỉ chứa các giá trị từ 1 đến n sao cho mỗi số chỉ xuất hiện đúng 1 lần và có thể viết dưới bất kỳ thứ tự nào.
Ví dụ với n=3 thì các hoán vị hợp lệ là [1,2,3]; [3,1,2], còn [1,2,2],[4,3,2,1] thì không
Bạn được cho một số nguyên dương n. Nhiệm vụ của bạn là đếm số lượng hoán vị độ dài n sao cho mỗi phần tử trong hoán vị có giá trị lớn hơn hoặc bé hơn tất cả các phần tử đứng trước nó trong hoán vị. Hay nói cách khác, gọi hoán vị là 1 dãy số p_1,p_2,\dots,p_n thì với mọi giá trị i thì thỏa mãn 1 trong 2 điều kiện sau:
- Với mọi j<i thì p_i>p_j
- Với mọi j<i thì p_i<p_j
Bạn nghĩ sẽ nhờ bạn như những người ra đề khác sao? Bạn nhầm rồi, đã giải được bài toán đó, liệu bạn có làm được như anh ấy không?
Input, Output và Subtasks
Input
- Dòng đầu tiên chứa số nguyên dương t (1 \leq t \leq 5\times 10^{4}) - số testcase
- T dòng sau, mỗi dòng chứa số nguyên dương n (1 \leq n \leq 10^{18}).
Output
Với mỗi testcase, in ra kết quả cần tìm trong một dòng. Vì kết quả có thể rất lớn nên bạn chỉ cần xuất ra kết quả sau khi chia lấy dư cho 10^9+7.
Sample và Explain
Sample Input
3
1
2
3
Sample output
1
2
4
Explain
- Trong testcase thứ ba, các hoán vị thỏa mãn bao gồm: [1,2,3]; [2,1,3]; [2,3,1]; [3,2,1]
Bình luận