Thiệp chúc mừng
Đề bài
Mô tả
Ở một ngôi làng nọ, hộ gia đình sống quây quần thành một vòng tròn, đánh số từ đến . Ban đầu, mức độ hạnh phúc của hộ thứ là (). Mỗi buổi sáng, mỗi hộ viết thiệp chúc mừng gửi cho các hộ khác, nhưng hẹn để thiệp chỉ đến tay người nhận sau giờ làm việc. Sau giờ làm, ai cũng mệt mỏi nên mức độ hạnh phúc của họ chỉ còn phụ thuộc vào những tấm thiệp nhận được: mức độ hạnh phúc của một hộ vào cuối ngày bằng tổng mức độ hạnh phúc của những người gửi thiệp cho hộ đó, tính tại thời điểm thiệp được viết.
Vào ngày , mỗi hộ chỉ viết thiệp cho hai hộ kề bên. Ở mỗi ngày tiếp theo, khoảng cách gửi thiệp tăng gấp đôi. Cụ thể, vào ngày , hộ viết thiệp cho hộ và hộ . Một hộ có thể viết hai tấm thiệp cho cùng một hộ trong cùng một ngày.
Cho số nguyên , hãy tính mức độ hạnh phúc của mọi hộ sau ngày (tức là vào cuối ngày ).
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và .
- Dòng tiếp theo chứa số nguyên .
Dữ liệu ra
In ra một dòng gồm số nguyên là mức độ hạnh phúc của các hộ sau ngày, lấy phần dư khi chia cho .
Ràng buộc
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 0 1 2 3 |
5 4 3 | Chỉ có ngày : hộ nhận thiệp từ hộ và hộ nên có ; tương tự hộ có , hộ có . |
| 3 1 1 2 3 |
7 8 9 | Sau ngày các mức là . Ngày khoảng cách là : hộ nhận từ hộ và hộ nên có ; hộ có , hộ có . |
Bình luận