Chia nhóm
Đề bài
Mô tả
Một trường học có học sinh, được đánh số từ đến . Hãy đếm số cách chọn một nhóm gồm ít nhất học sinh sao cho với mọi cặp học sinh và trong nhóm, và .
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên và (, ).
Dữ liệu ra
In ra một số nguyên là số cách chọn nhóm, lấy phần dư khi chia cho .
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 1 | 2 | Có học sinh, các cặp bị cấm là các cặp có hiệu bằng hoặc . Có thể chọn hoặc . |
| 3 3 | 14 | Ví dụ bổ sung (không có trong đề gốc). Hiệu không xảy ra giữa học sinh, nên chỉ cần không chọn hai học sinh liên tiếp: có tập như vậy (kể cả tập rỗng), trừ đi tập rỗng và tập một phần tử còn . |
Bình luận