Xông đất ngày Tết

Điểm: 1,16 (OI)

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

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

Input: stdin

Output: stdout

Nguồn bài:

Trên trời rơi xuống

Dạng bài

Ngôn ngữ cho phép

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

Bò đi xông đất vào ngày Tết. Khu phố nơi Bò ở có ~m~ ngôi nhà, Bò muốn xông đất đúng ~n~ ngôi nhà. Tuy nhiên Bò lại muốn xông đất sao cho không có ~2~ ngôi nhà nào kề nhau. Hỏi: Có bao nhiêu cách để xông đất thỏa mãn?

Kết quả theo module ~100003~ ~(10^{5} + 3)~

Input

Dòng đầu là số nguyên ~T~ (số test, ~T \le 10^{5})~.

Mỗi dòng trong ~T~ dòng sau chứa ~2~ số nguyên ~m~ và ~n~ ~(1 \le m~, ~n \le 10^{16})~

Output

Gồm ~T~ dòng, mỗi dòng là số cách tương ứng với từng test.

Sample Input

2
5 2
5 3

Sample Output

6
1

Bình luận

Hãy đọc nội quy trước khi bình luận.

1

dex111222333444555 đã bình luận lúc 13, Tháng 11, 2025, 14:52 ← chỉnh sửa →

Spoil thuật:

Với n, m lớn như vậy chúng ta cần một công thức tổ hợp:

Ta giả sử mỗi nhà được chọn như các vách ngăn thì nó sẽ có dạng như sau: Có tổng cộng m + 1 em bé. Giả sử mỗi em bé thứ i được xi viên kẹo (Đặt 1 TH bất kỳ cho mỗi ví dụ thỏa mãn các vách ngăn không kề nhau)

Ví dụ 1: n = 5, m = 2: Có tổng cộng n = 5 vị trí để 2 đặt vách ngăn: Vị trí: 1 2 3 4 5 1 2 3 4 5 _ _ _ _ _ -> +1 | +1 | +1 x1 = 1; x2 = 1; x3 = 1;

Ví dụ 1: n = 5, m = 3; Có tổng cộng n = 5 vị trí để đặt 3 vách ngăn: Vị trí: 1 2 3 4 5 1 2 3 4 5 _ _ _ _ _ -> | +1 +1 | | => x1 = 0; x2 = 2; x3 = 0; x4 = 0;

Từ 2 ví dụ trên thì ta cần đếm số cách x1 + x2 + x3 + ... + xm + x(m + 1) = n - m với x1, x(m + 1) >= 0 và xi >= 1 (2 <= i <= m)

Ta giả sử cho mỗi em bé từ 2 -> m đều nhận 1 viên kẹo thì nó sẽ chuyển thành bài toán chia kẹo Euler đếm số cách chọn x1 + x2 + x3 + ... xm + x(m + 1) = (n - m) - (m - 2 + 1) với xi >= 0 (1 <= i <= m + 1) => ta cần đặt thêm m vách ngăn vào giữa (n - m) - (m - 2 + 1) để chia m + 1 giá trị khác nhau vậy ta có tổng cộng m + (n - m) - (m - 2 + 1) space (_) => bài toán chuyển thành đếm số cách đặt m vách ngăn vào m + (n - m) - (m - 2 + 1) space vậy công thức sẽ là: C(m + (n - m) - (m - 2 + 1), m) = C(n - m + 1, m)

Nhưng n với m khá lớn ta không thể chạy tuyến tính được nhưng nhận thấy rằng số mod rất nhỏ => Định lý lucas. Có thể tìm hiểu ở đây: https://wiki.vnoi.info/translate/he/Lucas-theorem

20

PPAP_1264589 đã bình luận lúc 27, Tháng 12, 2021, 18:02

COMMENT NÀY SPOIL THUẬT !

Dạng bài: Tính ~nCk~ với ~n,k~ lớn và ~MOD~ nhỏ

-> Định lí Lucas

Xác định ~n~ và ~k~ của bài toán ?

-> Proof for number of ways to select k non-consecutive elements from n consecutive terms