TLEoj Contest #04 - Dãy bit
Xem PDF
Nộp bài
Điểm:
2500 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Tác giả:
Dạng bài
Bạn được biết m mô tả về dãy bit. Mỗi mô tả có thể thuộc 1 trong 2 loại sau:
- 1\ l\ r: Dãy bit con [l,r] chứa ít nhất 1 bit 0.
- 2\ l\ r: Dãy bit con [l,r] chứa ít nhất 1 bit 1.
Nhiệm vụ của bạn là đếm số lượng dãy bit có độ dài n sao cho nó khớp với mô tả trên.
Input, Output và Subtasks
Input
- Dòng đầu tiên chứa 2 số n,m\ (1\le n\le 10^{18};0\le m\le 10^5).
- Tiếp đó là m dòng, mỗi dòng là một mô tả thuộc 1 trong 2 loại trên (1 \le l \le r \le n).
Output
- In ra kết quả sau khi chia lấy dư cho 1234567891.
Scoring
- Subtask 1 (10\%): m = 0.
- Subtask 2 (15\%): 1 \le n \le 18; 0 \le m \le 36.
- Subtask 3 (20\%): 1 \le n \le 10^4.
- Subtask 4 (25\%): 1 \le m \le 10^4.
- Subtask 5 (30\%): Không giới hạn gì thêm.
Example
Input
3 2
1 1 2
2 2 3
Output
4
Note
- Có 4 dãy bit thỏa mãn là
001,010,011,101.
Bình luận