C11SEQ4 - C11SEQ4
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Sau khi được đố câu hỏi Violympic: “Có bao nhiêu số lẻ có 6 chữ số, các chữ số đứng cạnh nhau thì khác nhau”, Songuku95 nghĩ ra một bài toán mở rộng hơn:
Cho 2 số tự nhiên N, M. Tập hợp A={0,1,2,…,n}. Câu hỏi đặt ra là có bao nhiêu dãy X gồm k phần tử: {x1,x2,x3,…,xk} thỏa mãn:
- Xi thuộc tập hợp A ( 1 <= i <= k )
- Xk là số lẻ
- X1 khác 0
- Xi và X(i+1) là 2 số khác nhau ( với 1 <= i < k )
- 1 <= k <= N
Do kết quả có thể rất lớn nên các bạn chỉ cần in ra Kết quả mod M.
Lưu ý: 2 dãy X,Y khác nhau nếu tồn tại 1 vị trí p sao cho Xp khác Yp
Giới hạn:
- 20% số test có n,m <= 1000
- 20% số test tiếp theo có n,m <= 10^6
- 20% số test tiếp theo có n <= 10^6, m <= 10^15
- 20% số test tiếp theo có n <= 10^15, m <= 1000
- 20% số test còn lại có n,m <= 10^15
Input
Gồm 1 dòng duy nhất chứa hai số N,M ( 3 <= N,M <= 10^15 )
Output
Gồm 1 dòng duy nhất là kết quả bài toán
Example
Input: 3 123456 Output: 20
Giải thích: Có 20 số thỏa mãn là: 1, 3, 13, 21, 23, 31, 101, 103, 121, 123, 131, 201, 203, 213, 231, 301, 303, 313, 321, 323
- Người up: songuku95
- Nguồn bài: Nguyễn Duy Khánh